题目描述
一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0到n-1之内。
在范围0到n-1的n个数字中有且只有一个数字不在该数组中,请找出这个数字。
样例
输入:[0,1,2,4]
输出:3
算法1
直接进行遍历 O(n)
直接进行遍历, 发现有不符合条件的停止循环,输出结果。
C++ 代码
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
int i = 0;
for( ; i< nums.size(); i++)
if(nums[i] != i) break;
return i;
}
};
算法2
二分法 O(logn)
由于题目给定的是单调递增的序列, 缺少一个数字, 所以来说,左边的序列(缺失数字前面)的数值是等于下标的,右边序列的数值是不等于下标的,我们可以用这两个性质进行二分,找出这个临界点。 最后如果缺失的是最后一个数字,判断一下,此时二分就是返回的最后一个数字的下边, 我们只需要将最后一个下标进行++即可。
C++ 代码
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
if(!nums.size()) return 0;
int l = 0, r = nums.size() - 1; // 这里减1 不减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;
}
};