[Leetcode] 137. Single Number II

21-11-26
unsolved

Problem

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

Solution

풀이

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def num2bin(num):
            i = 0
            if num < 0:
                num = -num
                count[32] += 1
            while num > 0:
                num, r = divmod(num, 2)
                count[i] += r
                i += 1
                
        def bin2num(binary):
            mult = 1
            ans = 0
            for i in range(len(binary)-1):
                ans += mult*binary[i]
                mult *= 2
            return ans
        
        count = [0]*33
        for n in nums:
            num2bin(n)
        for i in range(len(count)):
            count[i] %= 3
        res = bin2num(count)
        return res if count[-1] == 0 else -res

기존에 Single 1이나 3의 경우는 1이 2개 있으면 0으로 소거된다는 점을 이용해 xor 연산을 이용하였다. 이번에는 1이 3번 나오면 소거되게 만든다. (위 풀이에서는 나중에 3으로 나눈 나머지를 구해 한번에 처리한다.)
count에서 i번째요소는 nums의 모든 원소에서 i번째 비트의 1 개수를 의미한다. 따라서 세 번 나오는 숫자는 무조건 비트를 3개 만들개 되고 마지막에 %3으로 소거된다.

Another Solution

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        #we need to implement a tree-time counter(base 3) that if a bit appears three time ,it will be zero.
        #curent  income  ouput
        # ab      c/c       ab/ab
        # 00      1/0       01/00
        # 01      1/0       10/01
        # 10      1/0       00/10
        # a=~abc+a~b~c;
        # b=~a~bc+~ab~c;
        
        a = 0
        b = 0
        
        for c in nums:
            ta=(~a&b&c)| (a&~b&~c)
            b=~a&~b&c|~a&b&~c
            a=ta
            
        return a|b

이 풀이에서는 digital circuit 로직으로 풀었다. 00 --> 01 --> 10 --> 00으로 순화하는 state 3개 만든다. 따라서 bit가 3개 쌓일 때마다 항상 초기화 해준다.