LeetCode 136. Single Number

题目

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

分析

找出重复数数组中只出现一次的数,典型的异或操作,异或操作的特点是可以交换可以结合,且偶数个相同的数异或一定为0,0 和一个数 num 的异或一定为 num

  • 输入:一个数组
  • 条件:数组中除了一个数只出现一次之外,其他数都出现过偶数次
  • 任务:找出这个只出现一次的数
  • 输出:这个只出现一次的数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return reduce(operator.xor, nums)
def singleNumber1(self, nums):
dic = {}
for num in nums:
dic[num] = dic.get(num, 0)+1
for key, val in dic.items():
if val == 1:
return key
def singleNumber2(self, nums):
res = 0
for num in nums:
res ^= num
return res
def singleNumber3(self, nums):
return 2*sum(set(nums))-sum(nums)
def singleNumber4(self, nums):
return reduce(lambda x, y: x ^ y, nums)

点评

singleNumber 和 singleNumber4 均是使用了异或操作,而 singleNumber1 使用了字典的方法,遍历两次就可以找出这个数