本文共 598 字，大约阅读时间需要 1 分钟。

题目描述

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0到n-1之内。

在范围0到n-1的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

样例描述

输入：[0,1,2,4]输出：3

思路

由于题目给的是递增数组，假设缺失的是x，如下

1. 边界判断，可能数组长度为0。
2. 若该递增数组不缺失，则缺失的是下一个数。
3. 时间复杂度是O(logn)。

代码

class Solution {       public int getMissingNumber(int[] nums) {       //判断边界        if(nums.length==0) return 0;        int l=0,r=nums.length-1;        while(l
   
    >1;            //若不相等，则肯定在右侧范围找            if(nums[mid]!=mid) r=mid;            else l=mid+1;        }        //若所有数都满足，则缺失的是下一个数        if(nums[r]==r) r++;        return r;    }}