剑指 Offer 53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

方法一：二分法

因为数组已经排序好了，可以通过二分法去确定，缺失的是哪一个数字。

根据题意，可以将数组分为两部分：

• 左子数组：$nums[i] = i$；
• 右子数组：$nums[i] \neq i$;

缺失的数字应当等于右子数组第一个元素的索引。

代码：

public int missingNumber(int[] nums) {
    if (nums[0] != 0){
        return 0;
    }
    if (nums[nums.length-1] != nums.length){
        return nums.length;
    }
    int i = 0, j = nums.length;
    while (i <= j) {
        int mid = (i + j) / 2;
        if (nums[mid] == mid) {
            i = mid + 1;
        } else {
            j = mid - 1;
        }
    }
    return i;
}

复杂度分析

• 时间复杂度$O(logN)$：二分法为对数级别复杂度。
• 空间复杂度$O(1)$：辅助变量占用常数大小的额外空间。

方法二：异或

异或有两条性质：① 0 ^ a = a ; ② a ^ a = 0 。

因为数组中的数字都是唯一的，将数组内的元素全部进行异或操作，然后在和 $0$ ~ n 进行异或，最后会只剩下那个不在数组中的数字。

public int missingNumber(int[] nums) {
    int xor = 0;
    for (int num : nums) {
        xor ^= num;
    }
    for (int i = 0; i <= nums.length; i++) {
        xor ^= i;
    }
    return xor;
}

复杂度分析

• 时间复杂度$O(N)$：算法进行 $2N$ 次循环。
• 空间复杂度$O(1)$：辅助变量占用常数大小的额外空间。