Single Number

题目描述

• single number 1, 除了一个，其他都出现两次
• single number 2, 除了一个，其他都出现三次
• single number 3, 除了两个，其他都出现两次
• single number 4, 除了三个，其他都出现三次

解题方法

1

xor

2

ones, twos, threes分别针对出现1，2，3次的情况来改变

核心代码：

for num in nums:
    # twos的bit在ones和当前num都为1的时候被set，本来twos的要保持，所以 |
    twos |= ones & num 
    # 如果是第二次出现就应该将ones的消去
    # 到第三次出现的时候, num里面为1的位现在已经是0，所以^会设为1
    ones ^= num
    # 在这一次ones和twos都为1的bit，就应该设threes上的相应bit为1了
    # ones和twos都要保持之前的各个bit，但是threes不需要
    threes = ones & twos 
    # 当有出现了3次的bit的时候，就应该将这一次ones和twos的相应bit清掉
    ones &= ~threes
    twos &= ~threes
return ones

3

两个数必然有某些bit不一样，这样我们通过xor的结果，找到第一个不为0的bit,再根据这个bit分类即可

xor = reduce(lambda x, y: x ^ y, nums)
last_set_bit = xor & ~(xor-1)
a, b = 0, 0
for num in nums:
    if num & last_set_bit:
        a ^= num
    else:
        b ^= num
return a, b

4

先找出一个数，另外两个同上

Solution

Reference