LeetCode Single Number II：位運算統計法解「只出現一次，其餘出現三次」

題目描述

給定一個整數數組，除了某個元素只出現一次外，其餘元素均出現三次。找出那個只出現一次的元素。要求：線性時間複雜度，常數空間複雜度。

核心思路：逐位統計 + 模 3 運算

整數以二進制存儲（32 位）。對於每一位（0~31），統計所有數在該位上 1 的總個數。因「其餘數出現三次」，該總個數對 3 取模後，餘數只能是 0 或 1。若為 1，說明目標數在該位為 1；若為 0，則為 0。將所有位的結果組合，即得答案。

算法步驟

1. 定義 int bitCount[32] = {0} 統計每位 1 的個數。
2. 遍歷數組每個數 num，對每位 i：bitCount[i] += (num >> i) & 1。
3. 構建結果：res |= (bitCount[i] % 3) << i。

完整代碼 (C++)

class Solution {
public:
    int singleNumber(vector& nums) {
        int bitCount[32] = {0};
        for (int num : nums) {
            for (int i = 0; i < 32; ++i) {
                bitCount[i] += (num >> i) & 1;
            }
        }
        int res = 0;
        for (int i = 0; i < 32; ++i) {
            res |= (bitCount[i] % 3) << i;
        }
        return res;
    }
};

舉例驗證

數組：[13, 13, 13, 8, 9, 9, 9]（二進制：13=1101, 8=1000, 9=1001）

結果二進制 1000 = 8，正確。

推廣：出現 k 次

同樣邏輯適用於「一個數出現 1 次，其餘出現 k 次」：統計每位 1 的個數，對 k 取模即可。

進階優化：有限狀態機 (O(1) 空間，無額外陣列)

用三個變量 ones, twos, threes 分別記錄各位上 1 出現 1 次、2 次、3 次的狀態。每次遍歷一個數 x：

twos |= ones & x;   // 出現兩次
ones ^= x;          // 出現一次
threes = ones & twos; // 出現三次
ones &= ~threes;    // 清除出現三次的位
twos &= ~threes;    // 清除出現三次的位

最終 ones 即為答案。此法無需 32 位陣列，更優雅。

總結

位運算統計法直觀易懂，時間 O(32n) ≈ O(n)，空間 O(32) ≈ O(1)。掌握「逐位獨立統計 + 模運算」思想，可解決所有「單一元素 vs 重複 k 次元素」的查找問題。