剑指 Offer 56 数组中数字出现的次数（异或）

数组中数字出现的次数 I

剑指 Offer 56 - I. 数组中数字出现的次数

相同的数异或为0，不同的异或为1，0和任何数异或等于这个数本身

所以，数组里面所有数异或 = 目标两个数异或 。 由于这两个数不同，所以异或结果必然不为0

假设数组异或的二进制结果为10010，那么说明这两个目标数从右向左数第2位bit是不同的

那么可以根据数组里面所有数的第二位bit为0或者1将数组划分为2个

这样做目标数必然分散在不同的数组中，而且相同的数必然落在同一个数组中

这两个数组里面的数各自进行异或，得到的结果就是答案

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int res = 0;
        for(int val : nums){
            res ^= val;
        }
        int index = 0;
        while((res & 1) == 0){
            // 这个循环用于找到两个目标数是哪个bit不同，用这个bit将两个目标数分开
            // 异或结果的某个bit为1，则说明两个目标数该bit不同
            res >>= 1;
            index++;
        }

        int num1 = 0;
        int num2 = 0;
        for(int val : nums){
            // 根据某个bit是否相同进行分组
            if(((val >> index)  & 1) == 1){
                num1 ^= val;
            }else{
                num2 ^= val;
            }
        }
        return {num1, num2};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

数组中数字出现的次数 II

数组中数字出现的次数 II

1. 方法一：位运算

0 ^ x  = x
x ^ x  = 0
x & ~x = 0
x & ~0 = x
1
2
3
4

一开始a = 0，b = 0

x第一次出现：a = (a ^ x) & ~b的结果为 a = x，此时因为a = x了，b = (b ^ x) & ~a的结果为b = 0；

x第二次出现：a = (a ^ x) & ~b, a = (x ^ x) & ~0，a = 0; b = (b ^ x) & ~a 化简， b = (0 ^ x) & ~0 ，b = x；

x第三次出现：a = (a ^ x) & ~b， a = (0 ^ x) & ~x ，a = 0; b = (b ^ x) & ~a 化简， b = (x ^ x) & ~0， b = 0

所以出现三次同一个数，a和b最终都变回了0；只出现一次的数，按照上面x第一次出现的规律可知a = x，b = 0；因此最后返回a

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0;
        int b = 0;
        for(int num : nums){
            a = (a ^ num) & ~b;
            b = (b ^ num) & ~a;
        }
        return a;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

2. 方法二：统计所有二进制表示中的位

建立一个长度为 32 的数组 countscounts ，通过以上方法可记录所有数字的各二进制位的 11 的出现次数

int count[32] = {0};
    for(int num : nums){
        for(int i = 31; i >= 0; i--){
        	// 索引小的下标，存放高位；索引大的下标，存放低位
            count[i] += (num & 1);
            num >>= 1;                
        }
    }
1
2
3
4
5
6
7
8

将 countscounts 各元素对 33 求余，则结果为 “只出现一次的数字” 的各二进制位
利用 左移操作 和 或运算 ，可将 counts 数组中各二进位的值恢复到数字 res 上

	for(int i = 0; i < 32; i++){
    	// 恢复时，要从高位开始恢复，即从小下标开始
        ans <<= 1;
        ans |= (count[i] % mod);
    }
1
2
3
4
5

用一个数组统计所有二进制表示中的位，出现多少次1全部记录下来，最后利用这个数组的统计数据进行恢复

例如：3,4,3,3

3 ：   11
4 ：  100
3 ：   11
3 ：   11
1
2
3
4

数组count元素为：[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,3,3]

最终恢复时，按照从高位到低位的顺序恢复，对count数组的元素mod 3，然后恢复即可

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int count[32] = {0};
        for(int num : nums){
            for(int i = 31; i >= 0; i--){
            	// 索引小的下标，存放高位；索引大的下标，存放低位
                count[i] += (num & 1);
                num >>= 1;                
            }
        }

        int ans = 0;
        int mod = 3;
        for(int i = 0; i < 32; i++){
        	// 恢复时，要从高位开始恢复，即从小下标开始
            ans <<= 1;
            ans |= (count[i] % mod);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

实际上，只需要修改求余数值 m ，即可实现解决除了一个数字以外，其余数字都出现 m 次 的通用问题