说了是增序的数组,那么一定是logn会让面试官满意,那么就是二分搜索了,左右端的判断条件是mid-left==nums[mid]-nums[left],如果相等,那么左边就是全的,目标就在右边(注意不要left=mid+1了)。while的退出条件是left和right相邻,结果就是nums[left]+1
这种情况只针对于缺少数字在中间的
如果缺的两端是没法判断的
所以一开始就判断一下两边。
class Solution {
public int getMissingNumber(int[] nums) {
if(nums==null || nums.length==0) return 0;
int left=0,right=nums.length-1;
if(nums[left]!=0) return 0;
if(nums[right]!=nums.length) return nums.length;
while((right-left)!=1){
int mid=left+(right-left)/2;
if((mid-left)==(nums[mid]-nums[left])){
//说明在右边
left=mid;
}else{
//说面在左边
right=mid;
}
}
//System.out.println(left+" "+right);
return nums[left]+1;
}
}