k-ésimo elemento faltante en una array desordenada

Dada una secuencia desordenada a[], la tarea es encontrar el k-ésimo elemento contiguo faltante en la secuencia creciente de los elementos del arreglo, es decir, considerar el arreglo ordenado y encontrar el k-ésimo número faltante. Si no hay k-ésimo elemento faltante, salida -1. 
Nota: Solo existen elementos en el rango de elemento mínimo y máximo a considerar. 
Ejemplos: 
 

Input: arr[] = {2, 4, 10, 7}, k = 5
Output: 9
Missing elements in the given array: 3, 5, 6, 8, 9
5th missing is 9.

Input: arr[] = {1, 3, 4}, k = 5
Output: -1

Método 1: ordene la array y use el enfoque utilizado en el k-ésimo elemento faltante en una array ordenada .
Método-2: 
 

1. Inserta todos los elementos en un conjunto_desordenado.
2. Encuentre el elemento mínimo y máximo de la array.
3. Recorre los elementos de mínimo a máximo. 
   • Compruebe si el elemento actual está presente en el conjunto o no.
   • Si no es así, compruebe si falta kth contando los elementos que faltan.
   • Devuelve el elemento actual si falta este.

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the sum
// of minimum of all subarrays
int findKth(int arr[], int n, int k)
{
 
    unordered_set<int> missing;
    int count = 0;
 
    // Insert all the elements in a set
    for (int i = 0; i < n; i++)
        missing.insert(arr[i]);
 
    // Find the maximum and minimum element
    int maxm = *max_element(arr, arr + n);
    int minm = *min_element(arr, arr + n);
 
    // Traverse from the minimum to maximum element
    for (int i = minm + 1; i < maxm; i++) {
        // Check if "i" is missing
        if (missing.find(i) == missing.end())
            count++;
 
        // Check if it is kth missing
        if (count == k)
            return i;
    }
 
    // If no kth element is missing
    return -1;
}
 
// Driver code
int main()
{
    int arr[] = { 2, 10, 9, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    cout << findKth(arr, n, k);
 
    return 0;
}

// Java implementation of the above approach
import java.util.*;
 
class GFG
{
 
    // Function to find the sum
    // of minimum of all subarrays
    static int findKth(int arr[], int n, int k)
    {
 
        HashSet<Integer> missing = new HashSet<>();
        int count = 0;
 
        // Insert all the elements in a set
        for (int i = 0; i < n; i++)
        {
            missing.add(arr[i]);
        }
 
        // Find the maximum and minimum element
        int maxm = Arrays.stream(arr).max().getAsInt();
        int minm = Arrays.stream(arr).min().getAsInt();
 
        // Traverse from the minimum to maximum element
        for (int i = minm+1; i < maxm; i++)
        {
            // Check if "i" is missing
            if (!missing.contains(i))
            {
                count++;
            }
 
            // Check if it is kth missing
            if (count == k)
            {
                return i;
            }
        }
         
        // If no kth element is missing
        return -1;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = {2, 10, 9, 4};
        int n = arr.length;
        int k = 5;
        System.out.println(findKth(arr, n, k));
    }
}
 
/* This code contributed by PrinciRaj1992 */

# Python3 implementation of the above approach
 
# Function to find the sum
# of minimum of all subarrays
def findKth( arr, n, k):
 
    missing = dict()
    count = 0
 
    # Insert all the elements in a set
    for i in range(n):
        missing[arr[i]] = 1
 
    # Find the maximum and minimum element
    maxm = max(arr)
    minm = min(arr)
 
    # Traverse from the minimum to maximum element
    for i in range(minm + 1, maxm):
         
        # Check if "i" is missing
        if (i not in missing.keys()):
            count += 1
 
        # Check if it is kth missing
        if (count == k):
            return i
     
    # If no kth element is missing
    return -1
 
# Driver code
arr = [2, 10, 9, 4 ]
n = len(arr)
k = 5
print(findKth(arr, n, k))
 
# This code is contributed by Mohit Kumar

// C# implementation of the above approach
using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG
{
 
    // Function to find the sum
    // of minimum of all subarrays
    static int findKth(int []arr, int n, int k)
    {
 
        HashSet<int> missing = new HashSet<int>();
        int count = 0;
 
        // Insert all the elements in a set
        for (int i = 0; i < n; i++)
        {
            missing.Add(arr[i]);
        }
 
        // Find the maximum and minimum element
        int maxm = arr.Max();
        int minm = arr.Min();
 
        // Traverse from the minimum to maximum element
        for (int i = minm + 1; i < maxm; i++)
        {
            // Check if "i" is missing
            if (!missing.Contains(i))
            {
                count++;
            }
 
            // Check if it is kth missing
            if (count == k)
            {
                return i;
            }
        }
         
        // If no kth element is missing
        return -1;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int []arr = {2, 10, 9, 4};
        int n = arr.Length;
        int k = 5;
        Console.WriteLine(findKth(arr, n, k));
    }
}
 
// This code has been contributed by 29AjayKumar

<?php
// PHP implementation of the above approach
 
// Function to find the sum
// of minimum of all subarrays
function findKth($arr, $n, $k)
{
 
    $missing = array();
    $count = 0;
 
    // Insert all the elements in a set
    for ($i = 0; $i < $n; $i++)
        array_push($missing, $arr[$i]);
 
    $missing = array_unique($missing);
     
    // Find the maximum and minimum element
    $maxm = max($arr);
    $minm = min($arr);
 
    // Traverse from the minimum to
    // maximum element
    for ($i = $minm + 1; $i < $maxm; $i++)
    {
        // Check if "i" is missing
        if (!in_array($i, $missing, false))
            $count += 1;
 
        // Check if it is kth missing
        if ($count == $k)
            return $i;
    }
     
    // If no kth element is missing
    return -1;
}
 
// Driver code
$arr = array(2, 10, 9, 4);
$n = sizeof($arr);
$k = 5;
 
echo findKth($arr, $n, $k);
 
// This code is contributed by Ryuga
?>

<script>
 
// javascript implementation of the above approach
 
// Function to find the sum
// of minimum of all subarrays
function findKth(arr, n, k)
{
 
    var missing = new Set();
    var count = 0;
 
    // Insert all the elements in a set
    for (var i = 0; i < n; i++)
        missing.add(arr[i]);
 
    // Find the maximum and minimum element
    var maxm = arr.reduce((a,b)=>Math.max(a,b));
    var minm = arr.reduce((a,b)=>Math.min(a,b));
 
    // Traverse from the minimum to maximum element
    for (var i = minm + 1; i < maxm; i++) {
        // Check if "i" is missing
        if (!missing.has(i))
            count++;
 
        // Check if it is kth missing
        if (count == k)
            return i;
    }
 
    // If no kth element is missing
    return -1;
}
 
// Driver code
var arr = [ 2, 10, 9, 4 ];
var n = arr.length;
var k = 5;
document.write( findKth(arr, n, k));
 
// This code is contributed by noob2000.
</script>

8