C ++中排序数组中缺少元素
假设我们有一个唯一编号排序的数组A，我们必须找到从数组最左边的编号开始的第K个缺失编号。因此，如果数组类似于[4,7,9,10]，并且k=1，则元素将为5。
为了解决这个问题，我们将遵循以下步骤-
n：=数组的大小，设置low：=0和high：=n–1
如果nums[n-1]–nums[0]+1–n<k，则
返回nums[n-1]+（k–（nums[n-1]–nums[0]+1–n））
而从低到高–1
中：=低+（高-低）/2
目前：=中–低+1
缺席：=nums[mid]–nums[low]+1–存在
如果不存在>=k，则为高：=中，否则，将k减小为不存在，低：=中
返回数字[低]+k
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int missingElement(vector<int>& nums, int k) {
int n = nums.size();
int low = 0;
int high = n - 1;
if(nums[n - 1] - nums[0] + 1 - n < k) return nums[n - 1] + (k
- ( nums[n - 1] - nums[0] + 1 - n)) ;
while(low < high - 1){
int mid = low + (high - low) / 2;
int present = mid - low + 1;
int absent = nums[mid] - nums[low] + 1 - present;
if(absent >= k){
high = mid;
}else{
k -= absent;
low = mid;
}
}
return nums[low] + k;
}
};
main(){
vector<int> v = {4,7,9,10};
Solution ob;
cout << (ob.missingElement(v, 1));
}输入值
[4,7,9,10] 1
输出结果
5