260. 只出現一次的數字 III

思路

1. 出現奇數次的數字有兩個（$a, b$），所以將所有數字亦或之後的結果會是 $a\oplus{b}$。
2. $a\neq{b}$，所以 $a\oplus{b}\neq0$

根據第二點，兩個數字間，一定至少有一位元是不相等的。
而不相等的位置，就是有 $1$ 的位置。
在那之前，先去找到 $a\oplus{b}$ 最右邊的 $1$ 所在的位置。

假設不同的位置在第 $\text{pos}$ 位，我們能將數字分成以下兩堆，並分別做亦或操作。

• 第 $\text{pos}$ 位為 $1$ 的數字。
• 第 $\text{pos}$ 位為 $0$ 的數字。

因為相等的數字會被消掉，兩堆最後剩下的數字，各自就會是 $a$ 與 $b$。

程式碼

位運算

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long long xor_all = 0;
        for(int num : nums) {
            xor_all ^= num;
        }
        int diff = xor_all & ~(xor_all - 1); // 避免 -xor_all 溢出導致 diff 出問題
        int a = 0, b = 0;
        for(int num : nums) {
            if(num & diff) a ^= num; // num & diff 只會是 diff or 0
            else b ^= num;
        }
        return {a, b};
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$