一、题目描述

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

示例 1:

输入: [0,1,3]

输出: 2

示例 2:

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

输出: 8

限制：

1 <= 数组长度 <= 10000

二、思路讲解

1、方法一

对于我这个算法小白来说，每次看见查找的题总要试试能不能暴力破解，这次成功了。

因为数组是递增的，索引和值对应不上，则必然缺失了；若全对上了，则必然缺失了n。

2、方法二

一说到查找，首选应该是二分查找。

承接上面的思路，如果二分位置的索引等于值，那么左边都不用查了，直接将右边作为子数组，继续二分即可；如果二分位置的索引不等于值，则将右边的指针左移一位，继续二分。直至两指针相遇，返回i指针对应的值即可。

三、算法描述

1、方法一

遍历数组nums，若索引与值不同，则返回索引；若能够走出循环，则必然数组里面必然是0~n-1的情况，则直接返回n        

四、Java代码实现

1、方法一

class Solution {
  public static int missingNumber(int[] nums) {
    //遍历数组
    for(int i=0; i<nums.length; i++) {
      //因为数组为递增数组，所以若索引小于它对应的值，则说明缺失了这个索引本该对应的数字
      if(i < nums[i]) {
        return i;
      }
    }
    //考虑[0]、[0,1]、[0,1,2]……的情况
    return nums.length;
    }
}

2、方法二

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

五、时空复杂度分析

1、方法一

时间复杂度：O(n)        遍历数组一次

空间复杂度：O(1)

2、方法二

时间复杂度：O(logn)        二分查找

空间复杂度：O(1)