LeetCode_Single Number II

Posted on | In | Views:

Single Number II

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
（只出现一次的数字(其余出现三次)）

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

Example:



1. 按位操作

ones / twos / threes 表示将数组中所有整形数转为二进制后，每个位上1出现次数为1/2/3次的情况；

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ones, twos, threes = 0, 0, 0
        
        for num in nums:
            twos |= ones & num
            ones ^= num
            threes = twos & ones
            # 当ones和twos中的某一位同时为1时表示二进制1出现3次，此时需要清零。
            ones &= ~threes
            twos &= ~threes
        
        return ones

2. 使用Python库Counter

1
2
3
4
5
6
7
8
9
from collections import Counter

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums_map = dict(Counter(nums))
        
        for num in nums_map:
            if nums_map[num] == 1:
                return num