题目
难度：★☆☆☆☆
类型：数组
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
解答
方案1：统计次数
我们准备一个字典，字典的键是列表中出现过的数字，值是该数字出现的次数，遍历数组统计每个数字出现的次数，最后返回出现过一次的数字即可。
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count = {} # 定义字典
for num in nums: # 遍历数组
if num in count: # 如果字典中存在当前记录
count[num] += 1 # 次数 + 1
else: # 否则
count[num] = 1 # 当前数加入到字典中，且出现次数为1
count = {v: k for k, v in count.items()} # 字典键值交换
return count[1] # 返回出现一次的数字
方案2：列表
准备一个列表，遍历数组，当前数字不在列表中时，加入列表，如果在列表中，则弹出列表中的该数，则最后只有出现过奇数次的数字留在列表中，返回该数即可。
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
temp = [] # 定义空列表
for num in nums: # 遍历数组
if num in temp: # 如果列表中存在当前数
temp.remove(num) # 移除
else: # 否则
temp.append(num) # 当前数加入到列表
return temp[0] # 返回列表中剩下的数字
方案3：巧用异或
异或运算有这样的特性：
交换律：a ^ b == b ^ a
相同数字异或为零：a ^ a == 0
数字异或零为该数字：a ^ 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
或者直接用字符串，内存占用多些。
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return eval('^'.join(map(str, nums)))
如有疑问或建议，欢迎评论区留言~
