LeetCode 260：只出現一次的數字 III（位運算解法）

題目描述

給定整數數組，其中恰好兩個元素只出現一次，其餘均出現兩次。找出這兩個元素。要求線性時間、常數空間。

位運算核心思路

1. 對所有數異或，得到 xor_all = a ^ b（a、b 為目標數）。
2. 找出 xor_all 中任一為 1 的位（如最低位 diff = xor_all & (-xor_all)）。
3. 根據該位將數組分為兩組：一組該位為 1，另一組為 0。a、b 落在不同組，且每組內其餘數成對出現。
4. 分別對兩組異或，即得到 a 和 b。

代碼實現 (C++)

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xor_all = 0;
        for (int x : nums) xor_all ^= x;
        int diff = xor_all & (-xor_all); // 保留最低位 1
        int a = 0, b = 0;
        for (int x : nums) {
            if (x & diff) a ^= x;
            else b ^= x;
        }
        return {a, b};
    }
};

複雜度

• 時間：O(n)
• 空間：O(1)