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

说明：

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

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

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

一开始我的想法是暴力枚举，python代码如下：

1
2
3
for i in nums:
    if(nums.count(i)==1):
        return i

后来一想，要求具有线性时间复杂度，对python的list.count() 不是很了解，万一这玩意本身的时间复杂度是O(n)，然后一来不就O(n^n)了？

随后想到先把这个数组排个序，然后模拟栈来实现（需要使用2个int的空间来存放结果）

1
2
3
4
5
6
7
8
9
10
11
12
13
def func(nums):
    nums = sorted(nums)
    cnt = 2
    stack = nums[0]
    for i in nums:
        if(i==stack):
            cnt = cnt-1
        else:
            cnt = cnt+1
            if(cnt==2):
                return stack
            stack = i
    return nums[-1]

居然很神奇的过了，用时88ms,超过22.81%，内存14.8MB超过48.18%。不过这显然不符合题目要求

想不出办法了，看看题解里面，有个叫做Hash表的算法，想到了在离散数学里面似乎看到过这玩意，就是比如[3,1,2,4,5]这个数组，根据值来确定存放元素的地址，3就放在a[3]的位置（1开始算）

这样的话，python里面用dict就可以实现,暂且不表

最骚的是直接用XOR，XOR还能满足交换律？！长见识了，考虑到每个重复元素只出现2次，就tql

1
2
3
4
5
def func(nums):
    ans = 0
    for i in nums:
        ans = ans^i
    return ans