[Leetcode/파이썬] 137. Single Number II

Single Number II

---

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

 

Example 1:

Input: nums = [2,2,3,2]
Output: 3

Example 2:

Input: nums = [0,1,0,1,0,1,99]
Output: 99

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• Each element in nums appears exactly three times except for one element which appears once.

 

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        dct = defaultdict(int)

        for num in nums :
            dct[num] += 1

        for key,val in dct.items() :
            if val == 1 :
                return key

        return -1

일반적인 카운팅 문제인듯 하다. 분명 시간복잡도 $O(N)$ 과 공간복잡도 $O(1)$로 풀어라고 되어있지만, 이 풀이가 가장 좋지 않나 생각한다. 모든 것을 충족시키는 풀이로는 비트를 활용한 풀이이며 

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ones = 0
        twos = 0

        for num in nums :
            ones = (ones ^ num) & ~twos
            twos = (twos ^ num) & ~ones
        
        return ones

이런식으로 된다고 한다. 

• & : AND
• ~ : NOT
• | : OR
• ^ : XOR

 

• ones : 한 번은 등장했지만 두 번은 등장하지 않은 숫자를 비트로 저장.
• twos : 두 번은 등장했지만 세 번은 등장하지 않은 숫자를 비트로 저장.
• 세 번 등장하는 숫자는 ones 와 twos에서 자동으로 제거된다.

이렇게 되면 ones에는 딱 한 번만 등장한 숫자가 저장되기 때문에 ones를 return 

사실 비트는 아직 잘 모르겠다...