Single Number寻找单数

Easy, bit manipulation

给定整数序列，其中除了一个数其他数都出现两次，找出该单数。复杂度O(N), 存储O(1)。

这道题本身是不难的，但是考虑到要控制复杂度为O(N)，就只能遍历一次，可是又不能分配新的存储，就不得不考虑有什么trick。这里借鉴Nkeys的思路，利用异或求解。因为A 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