LeetCode 單一數字 - 位運算異或(O(1) 空間)

問題描述

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

核心洞察：異或運算性質

• a ^ a = 0（相同數異或為 0）
• a ^ 0 = a（任何數與 0 異或不變）
• 異或滿足交換律和結合律，順序不影響結果。

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

代碼實現（C++）

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

擴展：出現三次 vs 一次

若其他數出現三次，需用位計數器（每位模 3），或有限狀態機。LeetCode 137 為該進階版。

複雜度

時間 O(n)，空間 O(1)。最優解。