題目出處

136. Single Number

難度

Easy

題目分類

hash-table, bit-manipulation

個人範例程式碼

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

Time Complexity

O(n)

算法說明

這題算是經典題目，因為經典做法太神奇了，
這題考的概念可以用 XOR 漂亮的解出來。

python 裡面，XOR 的符號表示做 「^」，
我們運用以下特性，同一個東西重複 XOR 兩次則變回原樣，
就可以在最小時間與空間解決此問題。

0 ^ a = a
a ^ a = 0
b ^ a ^ a = b

corner case 特殊情況處理

x

Boundary conditions/ Edge conditions 邊際情況處理

注意初始值應該為「0」而不是「1」

Reference

• C++ EASY SOLUTIONS – (SORTING , XOR , MAPS (OR FREQUENCY ARRAY))