在二进制中,异或(XOR)具有以下性质:
例如:
>>> 0 ^ 0
0
>>> 0 ^ 1
1
>>> 0 ^ 9
9
>>> 7 ^ 7
0
>>> 7 ^ 6 ^ 7
6
>>> (7 ^ 7) ^ 6
6
使用这个性质,可以完成下面这个算法题:
有一个无序的列表,里面有2n + 1个数。其中有n个各出现了2次,另有唯一一个数只出现了1次。使用时间复杂度为O(1),空间复杂度为O(1)的算法找出这个只出现1次的数。
例如这个列表为: [1,1,3,5,2,6,5,3,2]
,其中的 1
、 3
、 2
、 5
都出现了2次,而 6
只出现了1次。需要找出6。
使用异或算法非常简单:
>>> a = [1, 1, 3, 5, 2, 6, 5, 3, 2]
>>> s = 0
>>> for n in a:
... s = s ^ n
>>> s
6