给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
思路
很容易想到的2个方法是：
- 用list.count()方法统计只出现一次的个数，很不幸的是，这个超时了
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
X = [i for i in nums if nums.count(i) == 1]
return x[0]
- 用collections.Counter()，会返回一个字典，key为元素，value为元素出现的次数，只要找到value小于2的就好了，虽然没有超时，但是效率也不够让人满意，才超越了10%左右
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
x = collections.Counter(nums)
for key,value in x.items():
if value < 2:
return key
改进的版本
提交后看了最快的代码，思路是运用按位异或运算符，当两对应的二进位相异结果为1，真值表如下:
| a | b | c |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
可以看出如果有两个元素是相等的，按位异或的结果会是0，而0与任何数都等于这个数本身（也就是保存了这个数）
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
result = 0
for num in nums:
result = result ^ num
return result
