给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例

输入: [4,1,2,1,2]

输出: 4

解析

1）如果这道题没有不使用额外空间的限制，就有很多种解法，用hash记录次数最直接；

2）既然不能使用额外空间，说明要边遍历边计算，而且题目给出的数字很有意思，2m个成对数字，外加1个单的；

3）看到这个条件，应该能唤醒你的远古记录，三个数字的异或运算，得到的就是那个单独的数字。

代码示例 

# 逐个遍历异或相加
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for i in nums:
            res = res ^ i
        return res

# reduce简写形式
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x1,x2 : x1^x2, nums)

执行用时：44 ms, 在所有 Python3 提交中击败了 74.71% 的用户.

本文为 陈华 原创，欢迎转载，但请注明出处：http://edu.ichenhua.cn/read/381