[Leetcode] 136. Single Number

問題のショートカット

Hash Table

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

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