0～n-1中缺失的数字

题目描述

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

示例 1:

1 2	输入: [0,1,3] 输出: 2

示例 2:

1 2	输入: [0,1,2,3,4,5,6,7,9] 输出: 8

限制：
1 <= 数组长度 <= 10000

题目链接

Leetcode

题目解答

解法一

直接遍历，如果数组元素值与其对应的下标值不一致，缺失的数字就是下标值，否则缺失的就是数字中的最大值。

时间复杂度:$O(n)$ 空间复杂度:$O(1)$

class Solution {
    public int missingNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (i != nums[i]) {
                return i;
            }
        }
        return nums.length;
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.9 MB, 在所有 Java 提交中击败了64.01%的用户

解法二

1
2
3

a ^ a = 0; // 相同的两个数异或值为0
a ^ 0 = a; // 一个数与0异或值为自身
a ^ b ^ c = a ^ c ^ b; // 异或具有交换律

位运算，根据异或的性质，我们很容易使用异或运算找出两组数中缺失的元素。

时间复杂度:$O(n)$ 空间复杂度:$O(1)$

class Solution {
    public int missingNumber(int[] nums) {
        int miss = nums.length;
        for (int i = 0; i < nums.length; i++) {
            miss ^= i;
            miss ^= nums[i];
        }
        return miss;
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.8 MB, 在所有 Java 提交中击败了80.73%的用户

解法三

二分查找，定义左端点left，右端点right，中间点mid，如果中间点与其对应的数组元素值相等，说明中间点左侧没有缺失的数字，此时将左端点移动到中间点右侧1位，否则中间点左侧存在缺失的数字，将右端点移动到中间点左侧1位，左端点超过右端点所在位置，查找结束，左端点指向的位置就是缺失的数字。

时间复杂度:$O(\log{}n)$ 空间复杂度:$O(1)$

class Solution {
    public int missingNumber(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid == nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：39 MB, 在所有 Java 提交中击败了29.96%的用户