Programa en C++ para el k-ésimo elemento faltante en una array ordenada

Dada una secuencia creciente a[] , necesitamos encontrar el k-ésimo elemento contiguo faltante en la secuencia creciente que no está presente en la secuencia. Si no hay k-ésimo elemento faltante, salida -1. 

Ejemplos: 

Input : a[] = {2, 3, 5, 9, 10};   
        k = 1;
Output : 1
Explanation: Missing Element in the increasing 
sequence are {1,4, 6, 7, 8}. So k-th missing element
is 1

Input : a[] = {2, 3, 5, 9, 10, 11, 12};       
        k = 4;
Output : 7
Explanation: missing element in the increasing 
sequence are {1, 4, 6, 7, 8}  so k-th missing 
element is 7

Enfoque 1: Comience a iterar sobre los elementos de la array, y para cada elemento verifique si el siguiente elemento es consecutivo o no, si no, luego tome la diferencia entre estos dos y verifique si la diferencia es mayor o igual a k dada, luego calcular ans = a[i] + contar, de lo contrario iterar para el siguiente elemento.

#include <bits/stdc++.h>
using namespace std;
 
// Function to find k-th
// missing element
int missingK(int a[], int k,
             int n)
{
    int difference = 0,
        ans = 0, count = k;
    bool flag = 0;
     
    // iterating over the array
    for(int i = 0 ; i < n - 1; i++)
    {  
        difference = 0;
         
        // check if i-th and
        // (i + 1)-th element
        // are not consecutive
        if ((a[i] + 1) != a[i + 1])
        {
             
            // save their difference
            difference +=
                (a[i + 1] - a[i]) - 1;
             
            // check for difference
            // and given k
            if (difference >= count)
                {
                    ans = a[i] + count;
                    flag = 1;
                    break;
                }
            else
                count -= difference;
        }
    }
     
    // if found
    if(flag)
        return ans;
    else
        return  -1;
}
 
// Driver code
int main()
{
    // Input array
    int a[] = {1, 5, 11, 19};
     
    // k-th missing element
    // to be found in the array
    int k = 11;
    int n = sizeof(a) / sizeof(a[0]);
     
    // calling function to
    // find missing element
    int missing = missingK(a, k, n);
     
    cout << missing << endl;
     
    return 0;
}

14

Complejidad de tiempo: O(n), donde n es el número de elementos en la array. 

Enfoque 2: 

Aplicar una búsqueda binaria. Dado que la array está ordenada, podemos encontrar en cualquier índice dado cuántos números faltan como arr[índice] – (índice+1). Aprovecharíamos este conocimiento y aplicaríamos la búsqueda binaria para reducir nuestra búsqueda y encontrar ese índice desde el cual obtener el número que falta es más fácil.

A continuación se muestra la implementación del enfoque anterior:

// CPP program for above approach
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
// Function to find
// kth missing number
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);
     
    // If the total missing number
    // count is equal to k we can iterate
    // backwards for the first missing number
    // and that will be the answer.
    if(numbers_less_than_mid == k)
    {
       
      // To further optimize we check
      // if the previous element's
      // missing number count is equal
      // to k. Eg: arr = [4,5,6,7,8]
      // If you observe in the example array,
      // the total count of missing numbers for all
      // the indices are same, and we are
      // aiming to narrow down the
      // search window and achieve O(logn)
      // time complexity which
      // otherwise would've been O(n).
      if(mid > 0 && (arr[mid - 1] - (mid)) == k)
      {
        u = mid - 1;
        continue;
      }
      // Else we return arr[mid] - 1.
      return arr[mid]-1;
    }
     
    // Here we appropriately
    // narrow down the search window.
    if(numbers_less_than_mid < k)
    {
      l = mid + 1;
    }
    else if(k < numbers_less_than_mid)
    {
      u = mid - 1;
    }
  }
   
  // In case the upper limit is -ve
  // it means the missing number set
  // is 1,2,..,k and hence we directly return k.
  if(u < 0)
    return k;
   
  // Else we find the residual count
  // of numbers which we'd then add to
  // arr[u] and get the missing kth number.
  int less = arr[u] - (u + 1);
  k -= less;
   
  // Return arr[u] + k
  return arr[u] + k;
}
 
// Driver Code
int main()
{
    vector<int> arr = {2,3,4,7,11};
    int k = 5;
   
    // Function Call
    cout <<"Missing kth number = "<<
                        missingK(arr, k)<<endl;
    return 0;
}

8

Complejidad de tiempo: O(log(n)), donde n es el número de elementos en la array.

¡ Consulte el artículo completo sobre el k-ésimo elemento faltante en una array ordenada para obtener más detalles!