题目

难度：★☆☆☆☆

类型：数组

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

说明：

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

示例

示例 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)))

如有疑问或建议，欢迎评论区留言~