C++程序在已排序数组中查找第K个缺失元素

给定递增序列 a[] ，我们需要找到递增序列中第K个缺失的连续元素，其中该元素不在序列中。如果不存在第K个缺失的元素，则输出-1。

示例：

输入：a[] = {2, 3, 5, 9, 10};   
        k = 1;
输出：1
解释：递增序列中缺失的元素为 {1, 4, 6, 7, 8}。因此第K个缺失的元素是1。

输入：a[] = {2, 3, 5, 9, 10, 11, 12};       
        k = 4;
输出：7
解释：递增序列中缺失的元素为 {1, 4, 6, 7, 8}。因此第K个缺失的元素是7。

方法1： 开始迭代数组元素，对于每个元素检查下一个元素是否连续，如果不是，则取这两个元素之间的差，并检查该差是否大于或等于给定的K，如果是，则计算ans = a[i]+count，否则继续迭代下一个元素。

#include <bits/stdc++.h>
using namespace std;
 
// 寻找第k个缺失元素的功能函数
int missingK(int a[], int k,
             int n)
{
    int difference = 0,
        ans = 0, count = k;
    bool flag = 0;
     
    // 迭代数组
    for(int i = 0 ; i < n - 1; i++)
    {  
        difference = 0;
         
        // 检查第i个元素和第(i+1)个元素是否连续
        if ((a[i] + 1) != a[i + 1])
        {
             
            // 保存它们中间的差
            difference +=
                (a[i + 1] - a[i]) - 1;
             
            // 检查差和给定的K
            if (difference >= count)
                {
                    ans = a[i] + count;
                    flag = 1;
                    break;
                }
            else
                count -= difference;
        }
    }
     
    // 如果找到，则返回该元素
    if(flag)
        return ans;
    else
        return  -1;
}
 
// 主函数
int main()
{
    // 输入数组
    int a[] = {1, 5, 11, 19};
     
    // 数组中要查找的第k个缺失元素
    int k = 11;
    int n = sizeof(a) / sizeof(a[0]);
     
    // 调用函数找到缺失元素
    int missing = missingK(a, k, n);
     
    cout << missing << endl;
     
    return 0;
}

输出

时间复杂度： O(n)，其中n是数组中元素的数量。

空间复杂度： O(1)，因为没有使用额外的空间。

方法2：

应用二分查找。由于数组已排序，我们可以在任何给定的索引处找到多少个缺失的数字，即arr[index] – (index+1)。利用这个知识，我们可以应用二分查找来缩小寻找那个索引的范围，从而更容易地获取缺失的数字。

下面是上述方法的实现：

// 上述方法的 CPP 程序
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
// 查找第 k 个缺失数字的函数
int missingK(vector<int>& arr, int k)
{
  int n = arr.size();
  int l = 0, u = n - 1, mid;
   
  while(l <= u)
  {
    mid = (l + u)/2;
     
    int numbers_less_than_mid = arr[mid] -
                                    (mid + 1);
     
    // 如果缺失数字的总计数等于 k，我们可以向后迭代第一个缺失数字，这将是答案。
    if(numbers_less_than_mid == k)
    {
       
      // 为了进一步优化，我们检查前一个元素的缺失数字计数是否等于 k。例如： arr = [4,5,6,7,8]。
      // 如果您在示例数组中观察，所有索引的缺失数字的总计数都相同，我们旨在缩小搜索窗口并实现 O(logn) 的时间复杂度，
      // 否则将是 O(n) 的时间复杂度。
      if(mid > 0 && (arr[mid - 1] - (mid)) == k)
      {
        u = mid - 1;
        continue;
      }
      // 否则返回 arr[mid] - 1。
      return arr[mid]-1;
    }
     
    // 在此处适当地缩小搜索窗口。
    if(numbers_less_than_mid < k)
    {
      l = mid + 1;
    }
    else if(k < numbers_less_than_mid)
    {
      u = mid - 1;
    }
  }
   
  // 如果上限为负，这意味着缺失数字集合为 1,2,..,k，因此我们直接返回 k。
  if(u < 0)
    return k;
   
  // 否则，我们找到剩余数字的计数，然后将其添加到 arr[u] 中并获取缺失的第 k 个数字。
  int less = arr[u] - (u + 1);
  k -= less;
   
  // 返回 arr[u] + k
  return arr[u] + k;
}
 
// 主函数
int main()
{
    vector<int> arr = {2,3,4,7,11};
    int k = 5;
   
    // 调用函数
    cout <<"Missing kth number = "<<
                        missingK(arr, k)<<endl;
    return 0;
}

输出

时间复杂度： O(log(n))，其中 n 是数组中元素的数量。