[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๊ฐœ ์Œ“์ผ ๋•Œ๋งˆ๋‹ค ํ•ญ์ƒ ์ดˆ๊ธฐํ™” ํ•ด์ค€๋‹ค.

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ