[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๊ฐ ์์ผ ๋๋ง๋ค ํญ์ ์ด๊ธฐํ ํด์ค๋ค.
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Leetcode] 137. Single Number II), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@jong_p/Leetcode-137.-Single-Number-II์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ
์ธ ๋ฐ๊ฒฌ์ ์ ๋
(Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค