0136. Single Number - chasel2361/leetcode GitHub Wiki

Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:
Input: [2,2,1]
Output: 1

Example 2:
Input: [4,1,2,1,2]
Output: 4

這個問題如果要硬解的話，可以利用 dict 紀錄每個數出現的次數，最後回傳只出現一次的數，但如果利用 Bitwise Operation 的話可以更快速，且更省空間的解出答案

可以到這邊稍微回憶一下 XOR 的運算。額外要補充的部分是 XOR 結合率跟交換率的性質，所有的數都可以進行 XOR 運算，由於 XOR 必須前後僅一為真才回傳真，所以遇到重複的數就會回傳 0 ，又因為有交換率和結合率，運算的先後順序不影響計算結果，如此一來，最後的計算結果就會是唯一不重複的數。

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

這個寫法的時間複雜度是 O(N) ，空間複雜度是 O(1)

其實這個方法檢查的是"有哪一個數出現次數為奇數"，只是因為題目有限制出現次數最多為二，所以剛好可以適用。