LeetCode 260. Single Number III

原题链接：https://leetcode.com/problems/single-number-iii/

给出一个数组，其中有两个元素仅有一个，其它均有两个，要求找出仅有一个的两个数字。

首先最直观的解法，维护一个 set，遍历原数组，没有的加进去，有的移出，最后剩下的就是就是只有一个的了。
该方法的时间复杂度是 O(N)，空间复杂度也是 O(N)。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        result = set()
        for n in nums:
            if n in result:
                result.remove(n)
            else:
                result.add(n)
        return list(result)

题目说有O(1)空间复杂度的姐，可以想到的思路是 set 的添加和删除改成用一个常数来存储，用位操作来保存。

想了很久没想出来，最后去看了下讨论，终于理解了。
主要用到的是异或的一些特性。

以前有个经典例子，使用异或可以不借助中间变量交换两个数字：

In [203]: a, b = 1, 2
In [204]: a = a ^ b
In [205]: b = a ^ b
In [206]: a = a ^ b
In [207]: print a, b
2 1

一些其他特性：

0 ^ n = n
n ^ n = 0

题中仅有两个值是唯一的，其它都恰好只有两个。
因此全部进行异或的结果等于只异或两个答案的结果：

假定：

l = [a, b, c1, c2, d1, d2, ......, z1, z2]

中，a，b 是唯一的两个数，其它字母相同的是同样的数。
那么：

c1 ^ c2 = 0
...
z1 ^ z2 = 0

a ^ b ^ c1 ^ c2 ^ ... ^ z1 ^ z2 = a ^ b ^ (c1 ^ c2) ^ ... ^ (z1 ^ z2) = a ^ b ^ 0 ^ ... ^ 0 = a ^ b

因为 a 和 b 是不同的，即 a ^ b != 0，因此他们至少有一位是不同的，如对于 3 和 5 而言，

   011  -> 3
^ 101  -> 5   
----------
   110  -> 6

6 的右数第二、三位均为 1，即 3 和 5 的右数第二、三位是不同的，因此我们可以用这一位来区分 3 和 5。如取第二位，则为 10，值为2。

2 & 3 = 2
2 & 5 = 0

用回 a 和 b 表示即为：若 s = a ^ b，找出 s 从右到左第一个不为 0 的位：

mask = 1
while (s & mask == 0):
     mask = mask << 1

然后再次遍历数组，使用条件 num & mask == 0 将数字分为两组，分别取异或 s ，则可以得到 a 和 b。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        bit_num = 0
        for num in nums:
            bit_num ^= num
        mask = 1
        a = b = bit_num
        while (bit_num & mask == 0):
            mask = mask << 1
        for num in nums:
            if (num & mask):
                a ^= num
            else:
                b ^= num
        return [a, b]