Daily LeetCode – day0059 面试题 17.19. Missing Two LCCI

// 面试题 17.19. Missing Two LCCI
class Solution {
    public int[] missingTwo(int[] nums) {
        int xorsum = 0;
        int n = nums.length + 2;
        for (int num : nums) {
            xorsum ^= num;
        }
        for (int i = 1; i <= n; i++) {
            xorsum ^= i;
        }
        int lsb = (xorsum == Integer.MIN_VALUE ? xorsum : xorsum & -xorsum);
        int type1 = 0, type2 = 0;
        for (int num : nums) {
            if ((num & lsb) != 0) {
                type1 ^= num;
            } else {
                type2 ^= num;
            }
        }
        for (int i = 1; i <= n; i++) {
            if ((i & lsb) != 0) {
                type1 ^= i;
            } else {
                type2 ^= i;
            }
        }
        return new int[]{type1, type2};
    }
}

学习笔记：
今天这题也太难了吧，又是困难题。
找出1到n之间两个缺少的数，并且时间复杂度是n，空间复杂度是1。
看了官方的解法，啃了特别久终于懂了。
用到了大量位运算。
首先异或，异或会抵消。
所有xorsum先加全部数字，再加一遍1到n。相当于出现的数字搞了两次都抵消了。
剩下的xorsum就变成了a和b的异或了。
那么知道了有啥用呢？
a和b的异或，就说明a和b哪些位不同，本来a和b就肯定不同，所以肯定有1存在。
但可能有很多1，也有可能只有一个1。但我们要找出一位不同的来，也就是随便找一个1。
怎么找呢，就用x & -x来做，一个数和自己相反数按位与，结果就是只有一个1，那便是最右边最末尾的那个1。
找到了某一位是不同的之后，就把所有数字分成两类，一类是这一位是0的，一类是这一位是1的。
遍历一遍所有数字，再遍历一遍1到n，这样异或一遍之后。剩下的一组是a，另一组是b，答案就出来了。
这道题属实是太牛逼了，简直是面试神体，应该不提出苛刻的要求，让面试者来做，然后做完后层层递进提问。