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