只出现一次的数字

问题描述

260. 只出现一次的数字
     给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

解决方案

// 猜想1：计数法——失败，不清楚原因

// 要求找到出现两次的数，则异或排除用不了，只能用计数法

//猜想2：位运算

//其余元素均出现两次，目标元素出现一次，
//这意味着全员异或后，两个目标数字会凝聚到一起
//此时两数的异或结果的32个bit位中为1的位，就是两个目标数不同的位
//我们在异或结果中找某个1的位置，
//以此为依据，将nums数组分为两个小数组，
//此时，两个目标数就被分在了两个小数组中
//随后我们对两个小数组各自进行全员异或，
//此时，两个小数组中剩下的数字就是目标数

//方法1：

//我们找一个all_ret的第一个比特位等于为1的位置，
//然后把这个位置用flag记住，
//然后根据nums的各个元素的这个bit位是否等于flag为标准，
//把nums划分为两个部分。
//如此，因为划分依据是两个目标数相异后所得的，
//因此，划分后两个目标数就被动地归类到两个部分了；

//通俗地讲，我们用相异合并了两个目标数比特位上的不同点，
//把这个不同点作为一个标准
//用这个标准把nums划分为两个部分，
//所以两个目标数分别进入了划分后的部分
//最后从两个部分中找到我们的目标数。

//一言概之，拿一个中间结果推原因。

代码

// 思路1：计数法——失败，不清楚原因
// 要求找到出现两次的数，则异或排除用不了，只能用计数法
// class Solution {
// public:
//     vector<int> singleNumber(vector<int>& nums) {
//         map<int,int> s;
//         vector<int> arr(N,0);
//         vector<int> ret;
//         int i=0;
//         for(auto ns:nums)
//         {
//             s[ns]++;
//         }
//         for(auto ns2:arr)
//         {
//             if(arr[ns2]==2)
//             {
//                 ret[i++]=arr[ns2];
//             }
//         }

//         return ret;
//     }
// };


//思路2：位运算
//其余元素均出现两次，目标元素出现一次，
//这意味着全员异或后，两个目标数字会凝聚到一起
//此时两数的异或结果的32个bit位中为1的位，就是两个目标数不同的位
//我们在异或结果中找某个1的位置，
//以此为依据，将nums数组分为两个小数组，
//此时，两个目标数就被分在了两个小数组中
//随后我们对两个小数组各自进行全员异或，
//此时，两个小数组中剩下的数字就是目标数

//方法1：

//我们找一个all_ret的第一个比特位等于为1的位置，
//然后把这个位置用flag记住，
//然后根据nums的各个元素的这个bit位是否等于flag为标准，
//把nums划分为两个部分。
//如此，因为划分依据是两个目标数相异后所得的，
//因此，划分后两个目标数就被动地归类到两个部分了；

//通俗地讲，我们用相异合并了两个目标数比特位上的不同点，
//把这个不同点作为一个标准
//用这个标准把nums划分为两个部分，
//所以两个目标数分别进入了划分后的部分
//最后从两个部分中找到我们的目标数。

//一言概之，拿一个中间结果推原因。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int all_ret=0;
        for(int num:nums)
        {
            //全员异或的结果
            //此时all_ret存储了两个目标数异或后的的结果
            all_ret^=num;
        }

        //int flag=0;
        int i=0;
        for(i=0;i<32;i++)
        {
            //找到nums整体相异后all_ret的bit位第一个为1的位置
            if((all_ret>>i)&1==1)
            {
                //找到后用flag存储这个为1的位置
                //把flag的从右往左的第i个bit位，置为1
                //flag=(1<<i);
                break;
            }
        }

        //我们以flag为依据，将nums划分为两个部分
        vector<int> nums1;
        vector<int> nums2;
        for(auto n:nums)
        {
            if((n>>i)&1)
            {
                nums1.push_back(n);
            }
            else
            {
                nums2.push_back(n);
            }
        }

        int part1=0;
        int part2=0;
        //将两个部分各自异或
        //这两个部分各自异或的结果就是两个目标数
        for(int num:nums1)
        {
            part1^=num;   
        }        
        for(int num:nums2)
        {
            part2^=num;   
        }


        vector<int> vv;
        vv.push_back(part1);
        vv.push_back(part2);
        //vv.push_back(i);

        return vv;
    }
};