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

题目：

思路：

【1】最简单的直接遍历的方式：这个思路是基于，首先一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内，这就说明了这是一串连续的数字，且会与下标有一定联系，当不缺失的时候，下标与数值一 一对应，故直接遍历且比对下标即可。

【2】基于最简单的方式的理念，还可以使用Set辅助空间做也行，使用异或位运算进行两次遍历都可以，但是这样其实不如最简单的办法。

【3】当然其实这种有序的其实最好的优化其实是考虑二分查找。

代码展示：

基于二分查找的优化：

//时间0 ms击败100%
//内存42.4 MB击败35.37%
class Solution {
    public int missingNumber(int[] nums) {
       int l = 0;
       int r = nums.length - 1;
       while(l <= r){
           int mid = l + (r - l) / 2;
           if(nums[mid] == mid){
               l = mid + 1;
           }else{
               r = mid - 1;
           }
       }
       return l;
    }
}

基于最直接的方式衍生出来的：

//使用辅助空间的方式：
//时间3 ms击败4.31%
//内存41.7 MB击败98.20%
//时间复杂度：O(n)，遍历数组 nums 将元素加入哈希集合的时间复杂度是 O(n)，遍历从 0 到 n−1的每个整数并判断是否在哈希集合中的时间复杂度也是 O(n)，故是 O(2n) 等于O(n)。
//空间复杂度：O(n)，哈希集合中需要存储 n−1 个整数。
class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        int n = nums.length + 1;
        for (int i = 0; i < n - 1; i++) {
            set.add(nums[i]);
        }
        int missing = -1;
        for (int i = 0; i <= n - 1; i++) {
            if (!set.contains(i)) {
                missing = i;
                break;
            }
        }
        return missing;
    }
}


//使用位运算的方式
//时间0 ms击败100%
//内存42.5 MB击败14.24%
//时间复杂度：O(n)，需要对 2n−1 个数字计算按位异或的结果。
//空间复杂度：O(1)。
class Solution {
    public int missingNumber(int[] nums) {
        int xor = 0;
        int n = nums.length + 1;
        for (int i = 0; i < n - 1; i++) {
            xor ^= nums[i];
        }
        for (int i = 0; i <= n - 1; i++) {
            xor ^= i;
        }
        return xor;
    }
}

最简单的直接遍历的方式：

//时间0 ms击败100%
//内存42.4 MB击败26.47%
//时间复杂度：O(n)，其中 n 是数组 nums 的长度加 1。需要遍历数组 nums 一次寻找缺失的数字。
//空间复杂度：O(1)。
class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length + 1;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return n - 1;
    }
}