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

LeetCode 260. 只出現一次的數字 III

給定一個整數陣列 nums，其中恰好有兩個元素只出現一次，其餘所有元素均出現兩次。找出這兩個只出現一次的元素。

範例

輸入：nums = [1, 2, 1, 3, 2, 5]
輸出：[3, 5]（順序不重要）

進階要求

• 線性時間複雜度 O(n)
• 常數空間複雜度 O(1)

核心思路：異或分組

1. 將所有數字異或，得到 xor_all = a ^ b（a、b 為兩個唯一數字）。因 a ≠ b，xor_all 至少有一位為 1。
2. 找出 xor_all 中最低位的 1（即 diff = xor_all & (-xor_all)），該位上 a、b 必異（一為 0，一為 1）。
3. 根據該位將陣列分為兩組：該位為 1 的分一組，為 0 的分另一組。a、b 落入不同組，且每組中其餘數字均成對出現。
4. 對每組分別異或，即可得到 a 和 b。

C 語言實現

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumber(int* nums, int numsSize, int* returnSize) {
    int xor_all = 0;
    for (int i = 0; i < numsSize; i++) {
        xor_all ^= nums[i];
    }
    // 找出最低位的 1
    int diff = xor_all & (-xor_all);
    int *res = (int*)malloc(2 * sizeof(int));
    res[0] = res[1] = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] & diff) {
            res[0] ^= nums[i];
        } else {
            res[1] ^= nums[i];
        }
    }
    *returnSize = 2;
    return res;
}

複雜度分析

• 時間複雜度：O(n)，兩次遍歷陣列。
• 空間複雜度：O(1)，僅使用常數額外空間（不含輸出陣列）。

總結

利用異或運算的性質（x ^ x = 0、x ^ 0 = x）與位分組技巧，在線性時間、常數空間內解決問題，展現了位運算的強大威力。