一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。
示例 1:
输入: [0,1,3] 输出: 2
class Solution {
public int missingNumber(int[] nums) {
// 二分 对比nums[i] == i
if(nums == null || nums.length == 0)
return 0;
int l = 0, r = nums.length - 1;
while(l < r) {
int mid = l + (r -l) / 2;
if(nums[mid] != mid)
r = mid;
else
l = mid + 1;
}
// 尾部特殊处理
// [0 1 2] 3
if(nums[r] == r)
r++;
return r;
}
}