题目
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
例子
singleNumber([2,2,1]) -> 1
singleNumber([4,1,2,1,2]) -> 4
假设
- 输入的参数不为空
tips
- 你能想到不使dict的方法吗
答案
解法1
from functools import reduce
def singleNumber(nums):
return reduce(lambda x, y: x ^ y, nums)
性能:
- 时间复杂度
O(n)
- 空间复杂度
O(1)
关键点:
- 异或运算