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

链接：面试题 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 的值