当前位置:网站首页>剑指 Offer 56 数组中数字出现的次数(异或)

剑指 Offer 56 数组中数字出现的次数(异或)

2022-07-05 07:18:00 BugMaker-shen

数组中数字出现的次数 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};
    }
};

数组中数字出现的次数 II

数组中数字出现的次数 II

在这里插入图片描述

1. 方法一:位运算

0 ^ x  = x
x ^ x  = 0
x & ~x = 0
x & ~0 = x

一开始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;
    }
};

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;                
        }
    }

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

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

在这里插入图片描述

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

例如:3,4,3,3

3 :   11
4 :  100
3 :   11
3 :   11

数组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;
    }
};

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

原网站

版权声明
本文为[BugMaker-shen]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_42500831/article/details/125555888