0~n-1中缺失的数字

问题陈述

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

示例:

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

思路分析

对于查找类问题,可使用二分法解决。

由题意,该序列为0~n-1的递增序列中少掉了一个数字,故有,当nums[i]=i时可以知道前i个元素是没有缺失的,

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class solution{
public int getElementNotIn(int[] nums){
int i=0,j=nums.length-1;
int m=(i+j)/2;
while(i<=j){
if(nums[m]==m){
i=m+1;
}else{
j=m-1;
}
}
return i;
}

}