除了两个异类元素，其余都是成对出现的，O(n)时间复杂度找出它俩

发表于 | 分类于 | 阅读次数 |

#按位与（AND）：处理两个长度相同的二进制数，两个相应的二进位都为1，该位的结果值才为1，否则为0

0b1010 & 0b1100

8 #1000

#按位或(OR): 按位或处理两个长度相同的二进制数，两个相应的二进位中只要有一个为1，该位的结果值为1

0b1010 | 0b1100

14 #1110

#按位异或（XOR): 对等长二进制模式按位，或二进制数的每一位执行逻辑异按位或操作。操作的结果是如果某位不同则该位为1，否则该位为0

0b1010 ^ 0b1100

6 #0110

#移位：将一个二进制数中的每一位全部都向一个方向移动指定位，溢出的部分将被舍弃，而空缺的部分填入一定的值。

0b1010 << 2

40 #101000

0b1010 >> 2

2 #10

#取反(NOT): 一元操作，对二进制每位执行逻辑反，1->0, 0->1, 值得注意的是此操作符与”逻辑非（!）”操作符不同

~0b1010
-11 #10000000 00000000 00000000 00001011

type(0b1010)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# coding:utf-8
'''
一个数组仅有两个不同的值是仅含一个的.
其余值都是含两个的. 例如:[1, 1, 2, 2, 3, 4]

目标:
    找出那两个异常值.
要求:
    算法复杂度O(n)
    空间占用为常数,与n无关

为了不局限于比较对象,对hash值进行位操作.

'''

def XOR(a):
    """
    XOR of all elements of a.
    """
    xor = hash(a[0])
    for i in a[1:]:
        xor ^= hash(i)
    return xor

def find(a):
    r = XOR(a)
    pos = 0
    # pos 为r的2进制形式下从左往右首位不是0的位置.
    while r & 1 == 0:
        r = r>>1
        pos += 1
    num1, num2 = None, None
    # 将原数组按照二进制在pos位置是否为1分成两组
    for i in a:
        if (hash(i) >> pos) & 1 == 0:
            if num1 != None:
                num1 ^= hash(i)
            else:
                num1 = hash(i)
        else:
            if num2 != None:
                num2 ^= hash(i)
            else:
                num2 = hash(i)
    for i in a:
        if hash(i) == num1 or hash(i) == num2:
            yield i

if __name__ == '__main__':
    a = range(10)*2 + [11,12]
    print(a)
    for i in find(a):
        print(i)
    a = ['a', 'a', 'b', 'b', 'zsdf', 'fdfe']
    print(a)
    for i in find(a):
        print(i)