137. Single Number II

1.問題

• 給予一個整數(正, 負)序列, 每個數字重複3次, 找出只有出現一次的數字

2.想法

• 提問

• function header, parameter

• test input

• 觀察

  • 識別一個數字是否出現兩次可以用XOR, 但第三次時無法歸零, 因此可以想辦法讓第三次時歸0: & ~(上一次的狀態)

• 說明想法

• 測試計算複雜度

3.程式碼

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0;
        for (int i = 0; i < nums.size(); i++) {
            a = ((a ^ nums[i]) & ~b);
            b = ((b ^ nums[i]) & ~a);
        }
        
        return a | b;
    }
};