欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【位运算,异或】“只出现一次的数字” 的一类问题解决方法

程序员文章站 2022-04-05 15:56:54
...

问题的题目全部来自leetcode,题号已给出

异或的性质

两个数字异或的结果a^b是将 a 和 b 的二进制每一位进行运算,得出的数字。 运算的逻辑是如果同一位的数字相同则为 0,不同则为 1

异或的规律

1.任何数和本身异或则为0

2.任何数和 0 异或是本身

3.异或满足交换律。 即 a ^ b ^ c ,等价于 a ^ c ^ b

注意交换律

136. 只出现一次的数字

【位运算,异或】“只出现一次的数字” 的一类问题解决方法

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int i = 0 ;i<nums.length;i++){
            res ^= nums[i];
        }
        return res;
    }
}

举例解释:

17 ^ 19 ^ 17  =  17 ^ 17 ^ 19  = 19

137. 只出现一次的数字 II

【位运算,异或】“只出现一次的数字” 的一类问题解决方法
题解:暂时没看懂,放在这
https://leetcode-cn.com/problems/single-number-ii/solution/zhi-chu-xian-yi-ci-de-shu-zi-ii-by-leetcode/

面试题56 - I. 数组中数字出现的次数

【位运算,异或】“只出现一次的数字” 的一类问题解决方法
由于数组中存在着两个数字不重复的情况,我们将所有的数字异或操作起来,最终得到的结果是这两个数字的异或结果:(相同的两个数字相互异或,值为0)) 最后结果一定不为0,因为有两个数字不重复。

演示:

4 ^ 1 ^ 4 ^ 6 => 1 ^ 6

6 对应的二进制: 110
1 对应的二进制: 001
1 ^ 6  二进制: 111

此时我们无法通过111(二进制),去获得110001
那么当我们可以把数组分为两组进行异或,那么就可以知道是哪两个数字不同了。
我们可以想一下如何分组:

重复的数字进行分组,很简单,只需要有一个统一的规则,就可以把相同的数字分到同一组了。例如:奇偶分组。因为重复的数字,数值都是一样的,所以一定会分到同一组!

此时的难点在于,对两个不同数字的分组。

此时我们要找到一个操作,让两个数字进行这个操作后,分为两组。
我们最容易想到的就是 & 1操作, 当我们对奇偶分组时,容易地想到& 1,即用于判断最后一位二进制是否为1。来辨别奇偶。
你看,通过 &运算来判断一位数字不同即可分为两组,那么我们随便两个不同的数字至少也有一位不同吧!
我们只需要找出那位不同的数字mask,即可完成分组( & mask)操作。

为了操作方便,我们只去找最低位的mask: (mask就是上面演示的k)

num1: 101110    110     1111
num2: 111110    001     1001
mask: 010000    001     0010

由于两个数异或的结果就是两个数数位不同结果的直观表现,所以我们可以通过异或后的结果去找最低位的mask
通过mask的最低为将两个不同的数字分类到两个不同的组,对这两个组分别异或运算,得到每个组中只出现1次的数字

class Solution {
    public int[] singleNumbers(int[] nums) {
        //用于将所有的数异或起来
        int k = 0;
        
        for(int num: nums) {
            k ^= num;
        }
        
        //获得k中最低位的1
        int mask = 1;

        while((k & mask) == 0) {
            mask <<= 1;
        }
        
        int a = 0;
        int b = 0;
        
        for(int num: nums) {
            if((num & mask) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        
        return new int[]{a, b};
    }
}

练习:

面试题56 - II. 数组中数字出现的次数 II

645. 错误的集合

相关标签: leetcode解题