LeetCode Single Number II - 其餘元素出現三次，找唯一元素

題目大意

數組中除一個元素出現一次外，其餘均出現三次。找出單一元素。O(n) 時間、O(1) 空間。

方法一：逐位統計取模 (通用、易懂)

32 位整數每一位獨立統計 1 的個數，對 3 取模，餘數即為目標數該位的值。

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

方法二：有限狀態機 / 位掩碼優化 (O(1) 空間、無額外數組)

用兩個整數 ones、twos 表示「該位出現 1 次」和「出現 2 次」的掩碼。第三次出現時清零。

• twos |= ones & n：原本在 ones 中、今又出現 → 進入 twos。
• ones ^= n：翻轉 ones（出現 1→0，0→1）。
• threes = ones & twos：同時在 ones 和 twos 中 → 出現 3 次。
• ones &= ~threes; twos &= ~threes：清零第 3 次出現的位。

最終 ones 即為答案。

public class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for (int n : nums) {
            twos |= ones & n;
            ones ^= n;
            int threes = ones & twos;
            ones &= ~threes;
            twos &= ~threes;
        }
        return ones;
    }
}

複雜度

• 時間：O(n) — 方法一 32n 操作，方法二 5n 位運算。
• 空間：O(1) — 方法二無額外數組。

總結

Single Number II 考察位級狀態機設計。方法一直觀、易擴展（如出現 k 次），方法二極致優化、展示位運算功力。面試建議先講方法一，再推導方法二狀態轉移圖，最後給出無分支位運算代碼。