LeetCode Single Number：異或運算 O(n) 時間 O(1) 空間找唯一單數

問題描述

數組中只有一個數出現一次，其餘數均出現兩次。找出這個單一數。要求線性時間、常數空間。

核心性質：異或 (XOR) 運算

• x ^ x = 0（相同為 0）
• x ^ 0 = x（與 0 異或不變）
• x ^ y ^ x = y（交換律、結合律）

將所有數異或，成對數抵消為 0，剩下的就是單一數。

完整代碼 (C++)

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

異或運算經典應用總結

1. 無臨時變量交換：

   void swap(int& a, int& b) {
       if (&a == &b) return; // 防止同地址歸零
       a ^= b; b ^= a; a ^= b;
   }

2. 奇偶校驗：一組位異或結果為 1 ⇔ 1 的個數為奇數。
3. 找缺失數/重複數：結合索引異或。

總結

Single Number 是異或運算最經典的應用。理解「成對抵消、單一保留」的核心邏輯，不僅能秒殺此題，更是位運算技巧的入門基石。進階版 Single Number II (出現三次) 需用「逐位統計模 3」或「有限狀態機」。