[Leetcode] 136. Single Number

문제 바로가기

Hash Table

Time Complexity: $O(n)$
Space Complexity: $O(n)$

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        hashtable = dict()
        for num in nums:
            if num in hashtable:
                del hashtable[num]
            else:
                hashtable[num] = 1
        
        return list(hashtable.keys())[0]

Math

$2*(a+b+c)-(a+a+b+b+c) = c$

Time Complexity: $O(n)$
Space Complexity: $O(n)$

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        deduplicated = list(set(nums))
        timedSum = 0
        for num in deduplicated:
            timedSum += 2* num
        for num in nums:
            timedSum -= num
        return timedSum

Bit Manipulation

a ⊕ 0 = a
a ⊕ a = 0
a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b

cf) XOR 연산은 결합, 교환 법칙이 성립한다.

Time Complexity: $O(n)$
Space Complexity: $O(1)$

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res ^= num
        return res