LeetCode Single Number：位運算異或與 HashMap 兩種解法

題目大意

給定整數陣列，除一個元素出現一次外，其餘均出現兩次。找出那個只出現一次的元素。要求線性時間、常數額外空間。

解法一：位運算異或（最優）

性質：a ⊕ a = 0，a ⊕ 0 = a，滿足交換律與結合律。將所有元素異或，成對元素抵消為 0，剩下的即為單獨元素。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int x : nums) ans ^= x;
        return ans;
    }
};

• 時間：O(n)
• 空間：O(1)

解法二：HashMap 計數（通用、易擴展）

用 unordered_map 統計頻率，遍歷找頻率為 1 的鍵。可擴展到「出現三次找一次」等變體。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for (int x : nums) ++cnt[x];
        for (auto &p : cnt) if (p.second == 1) return p.first;
        return 0;
    }
};

• 時間：O(n) 期望
• 空間：O(n)

總結

• 異或解法優雅、空間最優，但僅適用於「其他元素出現偶數次」的情況。
• HashMap 解法直觀、通用，面試中可先給出 HashMap 再優化到異或。
• LeetCode 單號系列：Single Number II（三次/一次）需用位運算狀態機；Single Number III（兩個單獨）用異或分組。