给定一组数组，含有n种偶数个数字和2种奇数个数字，求这两种出现奇数次的数字_算法那个偶数两个两个奇数,求奇数

先看简单的情况

给定一组数组，含有n种偶数个数字和1种奇数个数字，求这种出现奇数次的数字

可以通过异或运算解决，相同的数异或为0，就保留下了奇数个的数字

#给定一组数组，含有n种偶数个数字和一种奇数个数字，求该种出现奇数次的数字
def getOddNum1(data):
    eor = 0
    for i in data:
        eor = eor ^ i
    print(eor)
1
2
3
4
5
6

给定一组数组，含有n种偶数个数字和2种奇数个数字，求这两种出现奇数次的数字

思路
假设这两种数是a和b
先对数组进行一遍异或运算，得到的结果是a^b
因为a和b是两种不同的数，那么a^b!=0，计作eor
说明a^b中至少存在某一位为1，假设这一位置是第x位
那么就可以把数组分为两组，x位不为0和x位不为1，计作A组和B组
在其中一组中作异或运算，那么就可以得到a|b，计作eor_p
（这一步比较难理解，可以这样思考，我把数分为了a,b和其他，因为其他的异或结果必然是0（因为偶数个相同数字），所以在计算第x位上的异或结果时，其他数字在该x位上存在偶数个0或者偶数个1，因此不会影响分组结果，因为分组后作异或运算，其他数字必然等于0，只会剩下a或者b）
然后得到另一个数字就是eor ^ eor_p

#给定一组数组，含有n种偶数个数字和2种奇数个数字，求这两种出现奇数次的数字
def getOddNum2(data):
    eor = 0
    for i in data:
        eor = eor ^ i
    # eor = a ^ b
    right = eor & (~eor + 1) # 获得最右侧的1，取补码进行与运算可得
    eor_p = 0
    # 将数分为该位为0和1的两组，得到a|b
    for i in data:
        if right & i == 0:
            eor_p = eor_p ^ i
    print(eor_p, eor_p^eor)
1
2
3
4
5
6
7
8
9
10
11
12
13

测试

if __name__ == '__main__':
    data1 = [1,1,1,2,2,3,3,4,4,4,5,5,6,6]
    getOddNum2(data1)
1
2
3

输出

4 1
1