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

問題描述

整數數組中，只有一個元素出現一次，其餘均出現兩次。找出這個單一元素。要求 O(n) 時間、O(1) 額外空間。

核心解法：異或運算 (XOR)

性質：x ^ x = 0，x ^ 0 = x，滿足交換律、結合律。
將所有元素異或：成對元素抵消為 0，剩下的即為單一元素。
ans = a[0] ^ a[1] ^ ... ^ a[n-1]

int singleNumber(vector& nums) {
    int ans = 0;
    for (int x : nums) ans ^= x;
    return ans;
}

擴展：元素出現三次，找出現一次的（LeetCode 137）

異或法失效（三次異或不為 0）。改用位計數法：

• 對 32 位分別統計所有數該位 1 的個數 cnt[i]。
• cnt[i] % 3 即為目標數第 i 位。
• 組裝 32 位得答案。

int singleNumberII(vector& nums) {
    int ans = 0;
    for (int i = 0; i < 32; i++) {
        int sum = 0;
        for (int x : nums) sum += (x >> i) & 1;
        if (sum % 3) ans |= (1 << i);
    }
    return ans;
}

時間 O(32n) = O(n)，空間 O(1)。通用於「出現 k 次 vs 1 次」問題。

Java 注意事項：無符號右移

Java 無無符號整型，負數右移會符號擴展。處理第 31 位（符號位）時需特殊處理，或使用 >>>> 無符號右移。上述代碼在 Java 中需調整：

int bit = (x >>> i) & 1; // 無符號右移

總結

• 出現兩次 vs 一次：異或一遍，最優雅、最快。
• 出現 k 次 vs 一次：32 位計數取模 k，通用、易懂。
• 兩種方法均為 O(n) 時間、O(1) 空間，滿足題目嚴格要求。