您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

Leetcode Single Number II：位運算找唯一出現一次的數

編輯：C++ 入門

問題描述

整數數組中，只有 1 個數出現 1 次，其餘數均出現 3 次。要求 O(n) 時間、O(1) 額外空間找到該數。

位運算核心思想

考慮二進制每一位。對於出現 3 次的數，每一位上 1 的總次數是 3 的倍數。唯一數的某位為 1 則該位總 1 數 ≡ 1 (mod 3)，為 0 則 ≡ 0 (mod 3)。

用兩個整數 ones, twos 模擬三進制計數器：

ones 第 k 位 = 1 表示該位總共出現 1 次 1（mod 3）
twos 第 k 位 = 1 表示該位總共出現 2 次 1（mod 3）
同時為 1 表示出現 3 次 → 清零

狀態轉移

新 twos = 舊 twos | (舊 ones & x)  // ones 有 1 且 x 有 1 → 進位到 twos
新 ones = 舊 ones ^ x             // 異或翻轉 ones
三進制溢出 = 新 ones & 新 twos    // 同時為 1 表示 3 次
新 ones &= ~溢出; 新 twos &= ~溢出 // 清零

參考代碼（C++）

class Solution {
public:
    int singleNumber(int A[], int n) {
        int ones = 0, twos = 0, threes = 0;
        for (int i = 0; i < n; i++) {
            twos |= ones & A[i];   // 進位
            ones ^= A[i];          // 異或累加
            threes = ones & twos;  // 檢測溢出（3次）
            ones &= ~threes;       // 清零
            twos &= ~threes;
        }
        return ones; // 最後 ones 保存模3為1的位
    }
};