LeetCode Single Number 只出現一次的數字 異或運算

問題

數組中除一個數出現一次外，其餘均出現兩次。找出該數。要求 O(n) 時間，O(1) 空間。

異或運算性質

• x ^ x = 0
• x ^ 0 = x
• 交換律、結合律成立

因此所有數異或後，成對數抵消為 0，剩下的即為單獨數。

代碼實現

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

擴展：Single Number II（其他數出現 3 次）

逐位統計模 3：bits[i] = (bits[i] + (x>>i&1)) % 3，重構結果。或用有限狀態機兩個變量 ones, twos 追蹤出現 1/2 次的位模式。

複雜度

• 時間 O(n)，單次遍歷
• 空間 O(1)，僅常數變量
• 位運算極快，無分支預測失敗