[Leetcode] 136. Single Number

5295 ワード
easy Hash Table Bit manipulation leetcode コーディングテスト テキストリンク
問題のショートカット

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
初期設定プロッタ
BetterTouchToolで、タッチパッドのジェスチャーをカスタマイズする