面试题56 - I. 数组中数字出现的次数

一个整型数组 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 <= 10000

这题我一开始卡了很久，并不知道该如何去做，看了题解才恍然大悟。
在完成本题前先做一道简单的题目热热身，那就是如果整个数组里只有一个数字出现了一次，其他都出现了两次，那只要所有数字求异或即可。得到的就是答案就是那个数字。
而如何通过这个结论来得到当有两个数字出现一次，其他数字出现两次呢，那就是分组异或。
由于这两个数字一定是不一样的，那么一定会在某一位上一个是1，一个是0，那么就按照这个依据来进行分类，分组进行异或求解得到的两个值就是了。 因为其他数字都会出现两次，而这两次毫无疑问都会分为一个组当中。
代码如下： 值得注意的点是 求异或判断是否等于的时候要加括号，因为判等的优先级高于位运算。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int x=0;
        int size=nums.size();
        for(int i=0;i<size;i++){
            x=nums[i]^x;
        }
        int b=1;
        while( (x&b) == 0 ){
            b=b<<1;
        }
        int ans1=0,ans2=0;
        for(int i=0;i<size;i++){
            if((nums[i]&b)==0){
                ans1^=nums[i];
            }
            else{
                ans2^=nums[i];
            }
        }
        return vector<int>{ans1,ans2};
        
    }
};

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。