Easy, bit manipulation

給定整數(shù)序列，其中除了一個(gè)數(shù)其他數(shù)都出現(xiàn)兩次，找出該單數(shù)。復(fù)雜度O(N), 存儲(chǔ)O(1)。

這道題本身是不難的，但是考慮到要控制復(fù)雜度為O(N)，就只能遍歷一次，可是又不能分配新的存儲(chǔ)，就不得不考慮有什么trick。這里借鑒Nkeys的思路，利用異或求解。因?yàn)锳 XOR A = 0， A XOR 0 = A。非常聰明的解法。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        for num in nums:
            res ^=num
        return res