题目描述

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

算法1

$O(n^2)$

C++ 代码

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {//首先计算所有数字的异或，因为只有两个不一样，
                                                    //所以最后结果肯定不为0. 并且可以根据最后结果将两个不一样的数分开。
                                                    //即res最后一位的1的位置，肯定一个数的这个位 是0， 一个是1.
        //首先计算所有的数字的异或。
        int n = nums.size();
        int res = nums[0];
        for(int i = 1; i < n; ++i){
            res ^= nums[i];
        }
        //找到最后一位的位置1，假定是k
        res = (-res & res); //lowbit操作

        //根据res将数组分为 k位是1  或者0  的两组， 怎么分呢，用res。找到一个第k位是1  和一个第k位是0 的数以便做连续异或
        int res1 = 0, res2 = 0;
        for(int i = 0; i < n; ++i){
            if((nums[i] & res) == 0) res1 = i;
            else res2 = i;
        }
        int num1 = nums[res1], num2 = nums[res2];

        //利用这两个数
        for(int i = 0; i < n; ++i){
            if(i != res1 && i != res2){
                if((nums[i] & res) == 0){
                    // cout<<"res1: "<<res1<<endl;
                    num1 ^= nums[i];
                }
                else {
                    // cout<<"res2: "<<res2<<endl;
                    num2 ^= nums[i];
                }
            }
        }
        return {num1, num2};

    }
};