原題鏈接：https://leetcode.com/problems/single-number-iii/

給出一個(gè)數(shù)組，其中有兩個(gè)元素僅有一個(gè)，其它均有兩個(gè)，要求找出僅有一個(gè)的兩個(gè)數(shù)字。

首先最直觀的解法，維護(hù)一個(gè) set，遍歷原數(shù)組，沒有的加進(jìn)去，有的移出，最后剩下的就是就是只有一個(gè)的了。
該方法的時(shí)間復(fù)雜度是 O(N)，空間復(fù)雜度也是 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)空間復(fù)雜度的姐，可以想到的思路是 set 的添加和刪除改成用一個(gè)常數(shù)來存儲(chǔ)，用位操作來保存。

想了很久沒想出來，最后去看了下討論，終于理解了。
主要用到的是異或的一些特性。

以前有個(gè)經(jīng)典例子，使用異或可以不借助中間變量交換兩個(gè)數(shù)字：

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

題中僅有兩個(gè)值是唯一的，其它都恰好只有兩個(gè)。
因此全部進(jìn)行異或的結(jié)果等于只異或兩個(gè)答案的結(jié)果：

假定：

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

中，a，b 是唯一的兩個(gè)數(shù)，其它字母相同的是同樣的數(shù)。
那么：

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

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

因?yàn)?a 和 b 是不同的，即 a ^ b != 0，因此他們至少有一位是不同的，如對(duì)于 3 和 5 而言，

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

6 的右數(shù)第二、三位均為 1，即 3 和 5 的右數(shù)第二、三位是不同的，因此我們可以用這一位來區(qū)分 3 和 5。如取第二位，則為 10，值為2。

2 & 3 = 2
2 & 5 = 0

用回 a 和 b 表示即為：若 s = a ^ b，找出 s 從右到左第一個(gè)不為 0 的位：

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

然后再次遍歷數(shù)組，使用條件 num & mask == 0 將數(shù)字分為兩組，分別取異或 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]