pythontip 100days-day29

题目

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

例子

singleNumber([2,2,1]) -> 1
singleNumber([4,1,2,1,2]) -> 4 

假设

  1. 输入的参数不为空

tips

  1. 你能想到不使dict的方法吗

答案

解法1

from functools import reduce
def singleNumber(nums):
    return reduce(lambda x, y: x ^ y, nums)
 

性能

  1. 时间复杂度O(n)
  2. 空间复杂度O(1)

关键点

  1. 异或运算