题目描述
一个长度为 n−1 的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围 0 到 n−1 之内。
在范围 0 到 n−1 的 n 个数字中有且只有一个数字不在该数组中,请找出这个数字。
样例
输入:[0,1,2,4]
输出:3
输入:[0,1,2,3]
输出:4
算法1
(二分) $O(logn)$
假设缺失数位x, 则x左边部分满足nums[i] == i,而x右边部分都不满足nums[i] == i,
因此我们可以二分出分界点 x 的值。
特殊情况:当所有数都满足nums[i] == i时,表示缺失的是 n。
C++ 代码
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
if(nums.empty()) return 0;
int n = nums.size();
int l = 0, r = n - 1;
while(l < r){
int mid = l + r >> 1;
if(nums[mid] == mid) l = mid + 1;
else r = mid;
}
//如果所有数都满足,则不满足的数为 n
if(nums[l] == l) l++; //这里l = r 都一样
return l;
}
};
算法2
(1)题目已知排好序,采用高斯公式,计算n+1个数的总和res.
(2)遍历数组,用res减去数组累加和, 最后差值即为缺失的数
时间复杂度 $O(n)$
C++ 代码
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
int n = nums.size() + 1;
int res = (n-1)*n / 2; //(首项+末项)*项数/2
for(auto x : nums) res -= x;
return res;
}
};