题目描述
一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0到n-1之内。
在范围0到n-1的n个数字中有且只有一个数字不在该数组中,请找出这个数字。
样例
输入:[0,1,2,4]
输出:3
算法1
(二分法) $O(logn)$
写了个lower_bound, 竟然发现不用特判hh,保证左边是nums[x] == x即可。
时间复杂度
传统的二分法,就是logn。
参考文献
C++ 代码
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 - l) / 2;
if (nums[mid] == mid) l = mid + 1;
else r = mid - 1;
}
return l;
}
};