题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。

你可以假设这两个数字一定存在。

样例

输入：[1,2,3,3,4,4]

输出：[1,2]

算法

(位运算) $O(n)$

• 所有数的异或值一定等于这两个只出现一次的数字的异或值
• 随便选择异或值中为1的某一位一定能将所有数分成两拨，一拨这一位是0，另一拨这一位是1

C++ 代码

class Solution {
public:
    int low_bit(int x) { return x & -x; }

    vector<int> findNumsAppearOnce(vector<int>& nums) {
        int c = 0;
        for (auto n : nums) c ^= n;
        int n1 = 0, n2 = 0;
        for (auto n : nums)
            if (low_bit(c) & n) n1 ^= n;
            else n2 ^= n;
        return {n1, n2};
    }
};