前往此题

解题思路

看到这道题第一反应是用哈希表来做，但是看到了题目后面要求空间复杂度为O(1)，瞬间绝望了！！

异或运算有一个特性，就是将两个相同的数字异或为0, 如果是不同的数字，那将进行异或运算：将十进制转为二进制后，对比每个二进制位，如果相同则为0，如果不同则为1。

比如： 0 0 1 0 ^ 0 0 0 1 = 0 0 1 1 等同于 0 0 0 1 ^ 0 0 1 0 = 0 0 1 1

这里我们可以得出： a ⊕ b = b ⊕ a

由于两个相同的二进制位进行异或运算的结果为0，我们借助这个特点可以遍历整个数组，对所有数字进行异或运算，相同的数字最终会被抵消掉，剩下的就是我们要找的那个两个不同数字之和。

nums = [4,1,3,4,6,3]

n = 0

for num in nums:
	n ^= num
	print(n)

但是本题需要找到两个只出现一次的数字，并不是它们的和。如果我们将这两个数字拆分到两个数组里，是不是可以解决这个问题了？

首先我们计算异或和，并将该值保存在变量xor中：

xor = 0
for num in nums:        
    xor ^= num

以[4,1,3,4,6,3]为例，最终的异或和为(4 ^ 4) ^ (3 ^ 3) ^ (1 ^ 6) = 7 = 0 1 1 1

其中:

• 1 = 0 0 0 1
• 6 = 0 1 1 0

既然有7是它们的异或结果，那么必然是两个不相同的数字通过异或运算得来的。因为7 = 0 1 1 1，它第一次出现不同是在倒数第一位。

现在只是理论，我们需要真正的把它给找出来，我们需要设置一个mask，这个mask始值为1 = 0 0 1 0，为什么初始值为1，因为它有且仅有一个1的二进制位，这样可以作为分组的参照物。

mask = 1
while xor & mask == 0:        
      mask <<= 1   

算法过程：

• 设置mask为1, 将它作为分组的参照物
• 执行遍历，当xor与运算mask 等于0的时候，mask向左移一位。

遍历结束后我们将得到我们想要的mask，最后再遍历数组nums, 将每个数字num与mask进行与或，如果为0说明num在此位为0，否则为1。这样两个数字就分开了，接下来再各自异或去掉相同的数字，剩下的就是我们要找的答案

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        xor = 0
        for num in nums:
            xor ^= num
        mask = 1
        while xor & mask == 0:
            mask <<= 1
        a, b = 0, 0
        for num in nums:
            if num & mask == 0: a ^= num
            else: b ^= num
        return a, b