leetcode 面试题 17.19. 消失的两个数字 (hard)(优质解法)

2023-12-24 19:31:27

链接:面试题 17.19. 消失的两个数字

代码:

class Solution {
    public int[] missingTwo(int[] nums) {
        int length=nums.length;
        int tmp=0;
        //将完整数据以及 nums 中的数据都进行异或,得到的就是缺失的两个数字 a^b 的结果
        for(int i=1;i<=length+2;i++){
            tmp^=i;
        }

        for(int i=0;i<length;i++){
            tmp^=nums[i];
        }

        //tmp 里的内容是 a^b (a,b 是缺失的两个数字)要分开 a,b 这两个数字
        //找到 tmp 中比特位为 1 的下标,代表 a 和 b 该下标的比特位不同
        int index=0;
        while(true){
            if(((tmp>>index)&1)==1){
                break;
            }
            index++;
        }

        //根据 index 下标的比特位进行分组,两个缺失的数字会被分开
        int[]ret=new int[2];
        for(int i=1;i<=length+2;i++){
            //异或所有 index 下标的比特位为 0 的数
            if(((i>>index)&1)==0){
                ret[0]^=i;
            }else{
                //异或所有 index 下标的比特位为 1 的数
                ret[1]^=i;
            }
        }

        for(int i=0;i<length;i++){
            if(((nums[i]>>index)&1)==0){
                ret[0]^=nums[i];
            }else{
                ret[1]^=nums[i];
            }
        }

        return ret;
    }
}

题解:

? ? ? ? 本题很明确,数组的内容应该是完整的从 1 ~ N 所有的整数,但现在缺了两个,本题通过位运算异或可以很巧妙的解决

? ? ? ? 首先需要了解异或的一些特性,a^0 = a, a^a = 0,简单来说异或的特性就是两个相同的数进行异或可以互相抵消

? ? ? ?以示例2为例,nums = 2,3 ,所以完整的数据应该是 1 ~ nums.length+2 ,即 1,2,3,4 ,我们将完整的数据以及 nums 中的所有数据都进行异或,其中 2,3 都有两个可以互相抵消,所以最终得到的结果就是 1^4 ,也就是我们要找的那两个缺失的数,现在首要的问题就是如何将我们要找的这两个数分离出来

? ? ? ? 进行异或操作时,相同的比特位为 0 ,不同的比特位为 1 ,我们现在有的数据是 tmp = a^b(a,b 是要获取的缺失的数),既然想要分离 a,b 的话,就需要找 a,b 的不同之处,我们可以找出 tmp 比特位为 1 的下标,比特位为 1 就代表该下标 a 和 b 的比特位不同,将该下标比特位为 1 的数和比特位为 0 的数分开,这样 a 和 b 肯定就分开了

????????由于除了 a 和 b 两个数以外,其余的数都是有两个的可以互相抵消,所以将比特位为 1 的数和比特位为 0 的数分别进行异或,最后就能得到 a,b 的值

文章来源:https://blog.csdn.net/q322359/article/details/135181099
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。