一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：
2 <= nums.length <= 10000

分组异或

思路

让我们先来考虑一个比较简单的问题：
如果除了一个数字以外，其他数字都出现了两次，那么如何找到出现一次的数字？
答案很简单：全员进行异或操作即可。考虑异或操作的性质：对于两个操作数的每一位，相同结果为 00，不同结果为 11。那么在计算过程中，成对出现的数字的所有位会两两抵消为 00，最终得到的结果就是那个出现了一次的数字。
那么这一方法如何扩展到找出两个出现一次的数字呢？
如果我们可以把所有数字分成两组，使得：
两个只出现一次的数字在不同的组中；
相同的数字会被分到相同的组中。

那么对两个组分别进行异或操作，即可得到答案的两个数字。这是解决这个问题的关键。

算法

1、先对所有数字进行一次异或，得到两个出现一次的数字的异或值。
2、在异或结果中找到任意为 1 的位。
3、根据这一位对所有的数字进行分组。
4、在每个组内进行异或操作，得到两个数字。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int ret = 0;
        for (int n : nums)
            ret ^= n;//先对所有数字进行一次异或，得到两个出现一次的数字的异或值。
        int div = 1;
        while ((div & ret) == 0)//(div & ret) == 1时候跳出来，选取的是「不为 0 的最低位」
            div <<= 1;
        int a = 0, b = 0;
        for (int n : nums)
            if (div & n)//如果该位为 1 就分到第一组，否则就分到第二组」
            //可以知道它们被分进了两组，所以满足了条件 1。
                a ^= n;//在每个组内进行异或操作，得到两个数字。
            else
                b ^= n;
        return vector<int>{a, b};
    }
};

复杂度分析

时间复杂度：O(n)，我们只需要遍历数组两次。
空间复杂度：O(1)，只需要常数的空间存放若干变量。