给出一个有序数组 A,数组中的每个数字都是 独一无二的,找出从数组最左边开始的第 K 个缺失数字。
示例 1:
输入:A = [4,7,9,10], K = 1
输出:5
解释:
第一个缺失数字为 5 。
示例 2:
输入:A = [4,7,9,10], K = 3
输出:8
解释:
缺失数字有 [5,6,8,...],因此第三个缺失数字为 8 。
示例 3:
输入:A = [1,2,4], K = 3
输出:6
解释:
缺失数字有 [3,5,6,7,...],因此第三个缺失数字为 6 。
提示:
1 <= A.length <= 50000
1 <= A[i] <= 1e7
1 <= K <= 1e8
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/missing-element-in-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int missingElement(vector<int>& nums, int k) {
int i = 0, n = nums.size(), ans;
for(i = 0; i < n-1; ++i)
{
if(nums[i+1]-nums[i]-1 < k)
k -= nums[i+1]-nums[i]-1;
else
{
ans = nums[i]+k;
return ans;
}
}
return nums[n-1]+k;
}
};
124 ms 29.6 MB
class Solution {
public:
int missingElement(vector<int>& nums, int k) {
int l = 0, r = nums.size()-1, mid, miss;
while(l <= r)
{
mid = l+((r-l)>>1);
miss = countmissing(nums, mid);
if(miss < k)
l = mid+1;
else if(miss > k)
r = mid-1;
else
return nums[mid]-1;
}
return nums[r]+k-countmissing(nums,r);
}
int countmissing(vector<int>& nums, int i)
{
return nums[i]-nums[0]-i;
}
};
144 ms 29.6 MB