136 Single Number

• 136 Single Number
  • 문제
  • 조건
  • 예제
  • 해결
    • 1st
      • 1 생각
      • 1 코드
      • 1 결과: 성공
    • 2nd 리트코드 다른 풀이
      • 2 코드

136 Single Number

문제

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

조건

• $1 \le nums.length \le 3 * 10^{4}$
• $-3 10^{4} \le nums[i] \le 3 10^{4}$
• Each element in the array appears twice except for one element which appears only once.

예제

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

Input: nums = [4,1,2,1,2]
Output: 4

Input: nums = [1]
Output: 1

해결

1st

1 생각

• 하나만 등장하는 요소를 찾으라는 건데, 비트 조작하고 어떻게 연관이 될까?
• 비트 조작 연산자은 아래 네 가지 가능
  • AND
  • OR
  • NOT
  • XOR
• XOR은 같으면 False가 되고, 다르면 True가 된다
  • 같은 걸 XOR 연산으로 없앨 수 있을 거 같은데, 어떻게?
  • 조건 상 딱 두번씩만 등장한다. 순서가 어떻든, XOR 연산을 하면, 두 번 등장하는 숫자들은 제거가 된다
  • 비트가 겹치더라도, 한 번만 등장하는 수는 겹치는 비트를 다시 토글 시키므로, 마지막에 남게 된다

1 코드

from typing import *
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        def decimal_to_binary(num, bit = 32):
            result = ""
            while num > 0:
                result = str(num % 2) + result
                num //= 2
            return result.rjust(bit, "0")

        ans = 0

        for num in nums:
            print("=====================================================")
            print("1. ans={}: {}".format(ans, decimal_to_binary(ans, 8)))
            print("2. num={}: {}".format(num, decimal_to_binary(num, 8)))
            ans ^= num
            print("3. ans={}: {}".format(ans, decimal_to_binary(ans, 8)))

        return ans
    
    
s = Solution()
print(s.singleNumber([2,3,5,2,4,5,3,7,1,7,4,6,6]))

"""
=====================================================
1. ans=0: 00000000
2. num=2: 00000010
3. ans=2: 00000010
=====================================================
1. ans=2: 00000010
2. num=3: 00000011
3. ans=1: 00000001
=====================================================
1. ans=1: 00000001
2. num=5: 00000101
3. ans=4: 00000100
=====================================================
1. ans=4: 00000100
2. num=2: 00000010
3. ans=6: 00000110
=====================================================
1. ans=6: 00000110
2. num=4: 00000100
3. ans=2: 00000010
=====================================================
1. ans=2: 00000010
2. num=5: 00000101
3. ans=7: 00000111
=====================================================
1. ans=7: 00000111
2. num=3: 00000011
3. ans=4: 00000100
=====================================================
1. ans=4: 00000100
2. num=7: 00000111
3. ans=3: 00000011
=====================================================
1. ans=3: 00000011
2. num=1: 00000001
3. ans=2: 00000010
=====================================================
1. ans=2: 00000010
2. num=7: 00000111
3. ans=5: 00000101
=====================================================
1. ans=5: 00000101
2. num=4: 00000100
3. ans=1: 00000001
=====================================================
1. ans=1: 00000001
2. num=6: 00000110
3. ans=7: 00000111
=====================================================
1. ans=7: 00000111
2. num=6: 00000110
3. ans=1: 00000001
1
"""

1 결과: 성공

Runtime: 128 ms
Memory Usage: 16.7 MB

2nd 리트코드 다른 풀이

2 코드

def singleNumber2(self, nums: List[int]) -> int:
    # 숫자가 두 번씩 등장해야 하므로 2를 set에 곱해준다
    return 2 * sum(set(nums)) - sum(nums) 

def singleNumber3(self, nums: List[int]) -> int:
    counts = Counter(nums)
    for num, times in counts.items():
        if times == 1:
            return num

• set을 사용하는 게 오히려 가장 빠르다

print(timeit.timeit(lambda: s.singleNumber([2,3,5,2,4,5,3,7,1,7,4,6,6]), number=100000))
print(timeit.timeit(lambda: s.singleNumber2([2,3,5,2,4,5,3,7,1,7,4,6,6]), number=100000))
print(timeit.timeit(lambda: s.singleNumber3([2,3,5,2,4,5,3,7,1,7,4,6,6]), number=100000))
"""
0.09166919999999999
0.0913351
0.2565687
"""