137. Single Number II

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

因為這邊是32-bit的整數,我們可以loop through每個bit去看nums裡面有多少數字有這個bit,統計該bit在nums中所有數字出現多少次之後,對3取餘數,在利用一個變數res去紀錄出現次數不為3整數倍的bit,最後操作完就可以得到指出現一次的數字。

int singleNumber(vector<int>& nums) { // time: O(n); space: O(1)
    int res = 0; // 32 bit integer
    for (int i = 0; i < 32; ++i) {
        int sum = 0;
        for (int num : nums) {
            sum += (num >> i) & 1;
        }
        res |= (sum % 3) << i;
    }
    return res;
}

延用上述方法的計算每個bit出現次數是否為3的整數倍來計算,上述方法中的sum最後只可能有0, 1, 2這三種值,在2進位表示中為00, 01, 10,所以利用2個32-bit正整數twos, ones分別代表2^1的位和2^0的位,然後loop一次nums數列,最後ones存的數就是出現一次的正整數。

int singleNumber(vector<int>& nums) { // time: O(n); space: O(1)
    int twos = 0, ones = 0;
    for (int num : nums) {
        ones = (ones ^ num) & ~twos;
        twos = (twos ^ num) & ~ones;
    }
    return ones;
}

Last updated

Was this helpful?