题目
- 一个长度为
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
代码
- 二分
//对于有序的数组, 都应该想到用二分法搜索
class Solution {
public int missingNumber(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// 数组下标是从0开始连续的向n增长，若相等范围区域继续向右靠
if (nums[mid] == mid) {
left = mid + 1;
}else {
right = mid - 1; // 不相等范围区域向左靠拢
}
}
return left;
}
}
代码分析：如果nums[mid] == mid说明在下标mid之前没有缺失数字。
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
if (nums.empty()) return 0;
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] != mid) r = mid;
else l = mid + 1;
}
if (nums[r] == r) r ++ ;
return r;
}
};
注意：当所有数都满足nums[i] == i时，表示缺失的是 nn。
