LeetCode 137. 只出現一次的數字 II：位運算統計法

LeetCode 137. 只出現一次的數字 II

給定一個整數陣列，除了某個元素只出現一次外，其餘元素均出現三次。找出那個只出現一次的元素。

進階要求

• 線性時間複雜度 O(n)
• 不使用額外記憶體（常數空間）

核心思路：位元計數取模

對於 32 位整數，統計陣列中所有數字在每個二進制位上 1 的總個數。因為出現三次的數字在每一位上的貢獻是 3 的倍數，所以每一位對 3 取模後的餘數，即為那個唯一數字在該位上的值。

具體步驟：

1. 建立長度為 32 的計數陣列 bits[32]，初始化為 0。
2. 遍歷輸入陣列，對每個數字的 32 位逐一檢查，累加到對應的 bits[i]。
3. 遍歷結束後，對每個 bits[i] 取模 3，得到的結果即為目標數字的二進制表示。
4. 將 32 位重新組合成整數返回。

C 語言實現

int singleNumber(int* nums, int numsSize) {
    int bits[32] = {0};
    int res = 0;
    for (int i = 0; i < 32; i++) {
        for (int j = 0; j < numsSize; j++) {
            bits[i] += (nums[j] >> i) & 1;
        }
        bits[i] %= 3;
        res |= (bits[i] << i);
    }
    return res;
}

複雜度分析

• 時間複雜度：O(32 * n) = O(n)，32 為常數。
• 空間複雜度：O(1)，固定大小的 32 元素陣列。

進階：有限狀態機（常數空間無額外陣列）

可用兩個變量 ones、twos 分別記錄「出現 1 次」和「出現 2 次」的位模式，利用位運算更新，最終 ones 即為答案。此法更優雅但理解難度較大，上述計數法更直觀易懂。

總結

位元計數取模法將「出現三次」轉化為模 3 運算，巧妙利用二進制位獨立性，在線性時間、常數空間內解決問題，是處理「N 次 vs 1 次」類問題的通用模板。