原題

給出2*n + 2個的數(shù)字，除其中兩個數(shù)字之外其他每個數(shù)字均出現(xiàn)兩次，找到這兩個數(shù)字。

樣例
給出 [1,2,2,3,4,4,5,3]，返回 1和5

解題思路

• 首先，通過位運算 - 異或之后，可以求出出現(xiàn)次數(shù)為1的兩個數(shù)的異或結(jié)果，如本例中1和5的異或結(jié)果，但是根據(jù)異或結(jié)果不能反推原來的兩個數(shù)是什么
• 但是我們可以通過求出lastBit 把原來的數(shù)組分成兩部分，一部分含有1一部分含有5，分別采用single number I的做法就可以求出這兩個數(shù)字
• 下面舉例子如何求出左邊數(shù)的第一個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的操作相當于把左邊數(shù)第一個1的數(shù)變?yōu)?，因為2的某次方一定是10...000，所以x & x - 1 == 0 可以判斷一個數(shù)是不是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