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

Math

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] missingTwo(int[] nums) {
        int n = nums.length + 2;

        int sum = n * (n + 1) / 2;

        int missingSum = 0;
        for (int num : nums) {
            missingSum += num;
        }

        int diff = sum - missingSum;
        int mid = diff / 2;
        int leftSum = mid * (mid + 1) / 2;
        for (int num : nums) {
            if (num <= mid) {
                leftSum -= num;
            }
        }

        return new int[]{leftSum, diff - leftSum};
    }
}

Bit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int[] missingTwo(int[] nums) {
        int n = nums.length + 2;

        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }
        for (int num = 1; num <= n; num++) {
            xor ^= num;
        }

        // xor 为两个缺失数字异或的结果
        int diffMask = xor & -xor; // 取出最低一个不同的比特位
        int x = 0;
        for (int num : nums) {
            if ((num & diffMask) != 0) {
                x ^= num;
            }
        }
        for (int num = 1; num <= n; num++) {
            if ((num & diffMask) != 0) {
                x ^= num;
            }
        }

        return new int[]{x, x ^ xor};
    }
}

References

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