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