LeetCode 137 Single Number II：其餘元素出現三次，位計數器法找出單一數字

題目描述

陣列中只有一個元素出現一次，其餘皆出現三次。找出該元素。要求線性時間、常數空間。

位計數器思路

對每個 bit 位（0~31），統計所有數字該位為 1 的總次數。因三次出現的數字每 bit 貢獻 3 的倍數，對 3 取餘後即為目標數字該 bit 的值。

代碼實作

class Solution {
public:
    int singleNumber(vector& nums) {
        int result = 0;
        for (int i = 0; i < 32; ++i) {
            int sum = 0;
            for (int n : nums) {
                if (n & (1 << i)) sum++;
            }
            if (sum % 3) result |= (1 << i);
        }
        return result;
    }
};

優化：有限狀態機（O(1) 空間、單次遍歷）

用兩個整數 ones, twos 追蹤每 bit 出現 1 次、2 次的狀態：

int singleNumber(vector& nums) {
    int ones = 0, twos = 0;
    for (int n : nums) {
        ones = (ones ^ n) & ~twos;
        twos = (twos ^ n) & ~ones;
    }
    return ones;
}

狀態轉移：00 → 10 → 01 → 00（對應 0→1→2→3 次）。

複雜度

• 時間：O(32·n) = O(n) 或 O(n)（狀態機版）。
• 空間：O(1)。

相關題目

• LeetCode 136：出現兩次，單次 XOR 即可。
• LeetCode 260：兩個單一數字，分組 XOR。