原题
给出2*n + 2个的数字，除其中两个数字之外其他每个数字均出现两次，找到这两个数字。
样例
给出 [1,2,2,3,4,4,5,3]，返回 1和5
解题思路
- 首先，通过位运算 - 异或之后，可以求出出现次数为1的两个数的异或结果，如本例中1和5的异或结果，但是根据异或结果不能反推原来的两个数是什么
- 但是我们可以通过求出lastBit 把原来的数组分成两部分，一部分含有1一部分含有5，分别采用single number I的做法就可以求出这两个数字
- 下面举例子如何求出左边数的第一个1，即给出10011100110 返回 00000000010
15 -> 1111 | 5 -> 0101 所以 15 ^ 5 = 1010 希望得到 0010
xor - (xor & xor - 1) = 1010 - (1010 & 1010 - 1)
= 1010 - (1010 & 1001)
= 1010 - 1000
= 0010
- x & x - 1的操作相当于把左边数第一个1的数变为0，因为2的某次方一定是10...000，所以
x & x - 1 == 0可以判断一个数是不是2的某次方
x = 1xxx...xxxx100
x - 1 = 1xxx...xxxx011
x & (x - 1) = 1xxx...xxx000
完整代码
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if not nums:
return -1
xor = 0
for item in nums:
xor ^= item
lastBit = xor - (xor & xor - 1)
group1, group2 = 0, 0
for item in nums:
if lastBit & item == 0:
group1 ^= item
else:
group2 ^= item
res = []
res.append(group1)
res.append(group2)
return res
