首页 > itarticle > leetcode_single number ii

leetcode_single number ii

admin 11月 13, 2020 0

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次的情况；

class :
    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 &= ~threes
            twos &= ~threes
        
        return ones

2. 使用Python库Counter

from collections import Counter

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