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

題目描述

給定整數數組 nums，其中恰有兩個元素只出現一次，其餘元素均出現兩次。找出這兩個只出現一次的元素。要求線性時間複雜度、常數空間複雜度。結果順序不限。

示例：nums = [1, 2, 1, 3, 2, 5] → 輸出 [3, 5] 或 [5, 3]。

核心思路：異或分組

1. 全局異或：將所有元素異或，相同數字抵消為 0，最終得到 xorAll = a ^ b（a、b 為兩個目標數）。
2. 找區分位：xorAll 中至少有一位為 1，表示 a、b 在該位不同。取最低位的 1（mask = xorAll & (-xorAll)）。
3. 分組異或：根據 mask 將數組分為兩組，a、b 落入不同組。各組內重複元素仍抵消，分別得到 a、b。

關鍵輔助函數

// 判斷 num 第 index 位是否為 1
bool isBit1(int num, unsigned int index) {
    return (num >> index) & 1;
}

// 找到 num 二進制中最低位 1 的索引
unsigned int findFirstBit1(int num) {
    int index = 0;
    while (((num & 1) == 0) && (index < 8 * sizeof(int))) {
        num >>= 1;
        ++index;
    }
    return index;
}

完整解法

class Solution {
public:
    vector singleNumber(vector& nums) {
        int xorAll = 0;
        for (int n : nums) xorAll ^= n;

        unsigned int diffBit = findFirstBit1(xorAll);
        int a = 0, b = 0;
        for (int n : nums) {
            if (isBit1(n, diffBit)) a ^= n;
            else b ^= n;
        }
        return {a, b};
    }
};

複雜度分析

• 時間：O(n)，兩次遍歷數組。
• 空間：O(1)，僅用常數額外變量。

相關題目

• LeetCode 136：只出現一次的數字（單目標，直接異或）
• LeetCode 137：只出現一次的數字 II（三次/一次，位計數法）