Q136 Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

解题思路：

这题看似简单，实则是一道比较有技巧的题目。

首先要求时间复杂度为 O(n)，空间复杂度为 O(1)。刚开始用Python写了一个时间复杂度 O(n^2) ，空间复杂度 O(1) 的，果然有一个case没有通过。

技巧性的关键，在于明白两个相同的数，进行异或操作，结果为0。因此，我们将所有的数字全部进行异或，然后，相同的数字最后都被消除了，异或的结果也就是剩下的那个单独的数字，返回即可。

一句话总结：偶消奇不消。

Python实现：

class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(1, len(nums)):
            nums[0] ^= nums[i]   # 相等的数字异或相消为0，最后剩下单一的数字
        return nums[0]

a = [2,1,2,3,1]
b = Solution()
print(b.singleNumber(a)) # 3