每日一题 4.28 数组中数字出现的次数

题目：

面试题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.看到这个题，第一想法是挺简单的，只要每个数从头开始(除自己)比较一遍，记录两个没有相同值的数就可以了，结果是可以实现的，但是时间复杂度是O(n)，肯定不行；
2.没有思路，看了已有的解题思路：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/jie-di-qi-jiang-jie-fen-zu-wei-yun-suan-by-eddievi/；下面的想法按照这个解题思路来的，也是首次尝试在C++中使用二进制计算的用法；
3.由于一定有两个数字相同，所以可以想到的就是异或运算，两个相同的数异或结果为0，那么尝试将所有数进行异或，由于只有两个不一样的数a,b，所以最后的结果就是a^(异或)b，但是这样我们还是不能取出这两个数，所以要想办法把数组分成两份，a,b分别在不同组，而相同的数又在一组就可以了；
4.而对于分组，最简单的就是按照奇偶分就可以了，相同的数一定在一个组里，而奇偶根据二进制最后一位0还是1就可以了，那么现在的问题就是怎么将a,b分在相同的组里；
5.二进制运算，由于a,b不相等，所以必定有不一样的位，找到一个不一样的位（一般找最低的非零位），然后按照这一位是0和1来进行分组（对于相同的数来说还是一样的，是另类奇偶分类）。
6.然后对两组分别异或，就可以得到a和b了。

代码：

解释：1.mask = k & (-k)原因，-k为k取反(k’)加1，先不考虑加一，k和k’与的结果为0，当k从最低位开始为0时，则对应k’为1,则加一产生进位，直到遇到k的第一个1，对应的k’为0，则不再产生进位，而k=1,k’=1，所以这一位为1，而其他位全为0

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        //全组异或，相当于a^b
        int k = 0;
        for(int i = 0; i < nums.size(); i++){
            k ^= nums[i];
        }
        //求解最低非0位
        int mask= k & (-k);
        //记录a,b
        vector<int> a(2, 0);
        //分组
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] & mask){
                // cout << nums[i] << endl;
                a[0] ^= nums[i];
            }
            else{
                a[1] ^= nums[i];
            }
        }
        return a; 
    }
};

思考：

1.这是第一次在C++中考虑使用二进制运算来完成算法，要有这样的思维；小心思维定势！