算法题位运算-数组中数字出现的次数

数组中数字出现的次数

题目描述：一个整型数组 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]

来源：力扣（LeetCode）
题目链接：https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof

解题思路

说实话，对于这种题我第一眼看见的感觉脑子里会直接闪过暴力遍历的方法，但是用这个方法先不说不满足题意，而且显得自己像个呆鸡。总结之前的题目经验，第二时间想到使用哈希表来做，但是开辟哈希表的话空间复杂度就不满足O(1)的要求。所以暂时的最佳解法是使用位运算的方法来解决。因为之前位运算使用的比较少，所以思路上并不开阔，理解起来比较绕，所以在这里把理顺的思路写出来，记录一下。
解这个题需要知道异或（XOR） ^ 的运算规则：
1、交换律。 A ^ B = B ^ A
2、结合律。 (A ^ B) ^ C = A ^ (B ^ C)
3、对于任何数都有 A ^ 0 = A, A ^ A = 0
4、所以 A ^ B ^ B = XOR ^ B -> A = XOR ^ B

再知道运算规则过后，假设数组内的不重复的数为A和B，那么对数组元素全部进行异或即 nums[0] ^ nums[1] ^ … ^nums[n-1] = A ^ B。接下来就是取巧的地方了，获取AB异或值最低位为1的数，即获取AB两个数位不相同的最低位div。用这个最低位对AB进行分组，A&div 和 B&div 会等于0或者1，同时还可以对数组内的元素进行分组，相同的数值会分到同一组，那么对这个A组和B组的元素分别进行异或，那么两个组最后剩下的就只有A 和 B了。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int xorAB = 0; // 定义AB的异或值，即整个数组的异或值
        for(int num:nums) { //求异或值
            xorAB ^= num;
        }

        int div = xorAB & (-xorAB); //定义分组方法，这种方法还有别的办法，只要能区分出AB两个组就可以。
        int A = 0; //
        for(int val:nums) { 
            if((div&val) != 0) { // 对A组内的所有数进行异或，求的A的值
                A ^= val;
            }
        }
        return vector<int>{A, xorAB^A}; // xorAB^A 就是B
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18