[Leetcode] 136. Single Number

haebin·2021년 4월 4일
0

코딩테스트

목록 보기
40/65

문제 바로가기

Hash Table

Time Complexity: O(n)O(n)
Space Complexity: O(n)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)=c2*(a+b+c)-(a+a+b+b+c) = c

Time Complexity: O(n)O(n)
Space Complexity: O(n)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)O(n)
Space Complexity: O(1)O(1)

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

0개의 댓글