Encuentre el entero positivo más grande x que falta en una array no ordenada de modo que min(arr[]) < x < max(arr[])

Dada una array arr[] que contiene números enteros. La tarea es encontrar el entero positivo más grande x que falta en la array de modo que min(arr[]) < x < max(arr[]) .

Ejemplos

Entrada: arr[] = {2, 3, 7, 6, 8}
Salida: 5
Explicación: 5 es el entero positivo más grande que falta en arr[] y 2 < 5 < 8.

Entrada: arr[] = { 2, 3, -7, 1, 4 }
Salida: -1

Enfoque ingenuo: ordene la array de forma descendente y devuelva el primer número positivo que falta. Si no falta ninguno, devuelve -1 .

Complejidad de tiempo: O(N logN) 
Complejidad de tiempo: O(1)

Enfoque eficiente: este problema se puede resolver utilizando Hashing . Cree un Hashmap de todos los elementos positivos en la array dada. Después de construir Hashmap, mire en el HashMap desde el revés y devuelva el primer número positivo que falta. Si no falta ninguno, devuelve -1 .

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find missing positive integer
int firstMissingPositive(vector<int>& nums)
{
    int n = nums.size();
 
    // Map to store the elements
    map<int, int> m;
    for (int i = 0; i < n; i++) {
        if (m.find(nums[i]) == m.end()) {
            m.insert({ nums[i], 1 });
        }
    }
 
    int ans = 0;
 
    // Traversing the Hashmap from reverse
    for (ans = m.rbegin()->first; ans > 0; ans--) {
        if (m.find(ans) == m.end())
            break;
    }
    return ans;
}
 
// Driver code
int main()
{
    vector<int> arr = { 2, 3, 7, 6, 8 };
    int missing = firstMissingPositive(arr) == 0
                      ? -1
                      : firstMissingPositive(arr);
    cout << missing;
    return 0;
}

// Java program for above approach
import java.util.*;
class GFG
{
 
  // Function to find missing positive integer
  public static int firstMissingPositive(int[] nums)
  {
    int n = nums.length;
 
    // Map to store the elements
    HashMap<Integer, Integer> m = new HashMap<>();
    for (int i = 0; i < n; i++) {
      if (m.containsKey(nums[i]) == false) {
        m.put(nums[i], 1);
      }
    }
    int ans = 0;
 
    for (Map.Entry<Integer, Integer> temp :
         m.entrySet()) {
      ans = Math.max(ans, temp.getKey());
    }
 
    // Traversing the Hashmap from reverse
    for (; ans > 0; ans--) {
      if (m.containsKey(ans) == false)
        break;
    }
    return ans;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int[] arr = { 2, 3, 7, 6, 8 };
    if (firstMissingPositive(arr) == 0)
      System.out.print(-1);
    else
      System.out.print(firstMissingPositive(arr));
  }
}
 
// This code is contributed by Taranpreet

# Python program for above approach
 
# Function to find missing positive integer
def firstMissingPositive(nums):
    n = len(nums)
 
    # Map to store the elements
    m = {}
    for i in range(n):
        if (nums[i] not in m):
            m[nums[i]] = 1
 
    ans = 0
    for itm in m.keys():
        ans = max(ans, itm)
     
    # Traversing the Hashmap from reverse
    while(ans >= 0):
        if (ans not in m):
            break
        ans -= 1
 
    return ans
 
# Driver code
arr = [2, 3, 7, 6, 8]
missing = -1 if firstMissingPositive(arr) == 0 else firstMissingPositive(arr)
print(missing)
 
# This code is contributed by shinjanpatra

// C# program for above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Function to find missing positive integer
  public static int firstMissingPositive(int[] nums)
  {
    int n = nums.Length;
 
    // Map to store the elements
    Dictionary<int, int> m = new Dictionary<int, int>();
    for (int i = 0; i < n; i++) {
      if (m.ContainsKey(nums[i]) == false) {
        m.Add(nums[i], 1);
      }
    }
    int ans = 0;
 
    foreach (KeyValuePair<int, int> temp in
             m) {
      ans = Math.Max(ans, temp.Key);
    }
 
    // Traversing the Hashmap from reverse
    for (; ans > 0; ans--) {
      if (m.ContainsKey(ans) == false)
        break;
    }
    return ans;
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    int[] arr = { 2, 3, 7, 6, 8 };
    if (firstMissingPositive(arr) == 0)
      Console.Write(-1);
    else
      Console.Write(firstMissingPositive(arr));
  }
}
 
// This code is contributed by 29AjayKumar

<script>
        // JavaScript program for above approach
 
        // Function to find missing positive integer
        const firstMissingPositive = (nums) => {
            let n = nums.length;
 
            // Map to store the elements
            let m = {};
            for (let i = 0; i < n; i++) {
                if (!(nums[i] in m)) {
                    m[nums[i]] = 1;
                }
            }
 
            let ans = 0;
            for (let itm in m) ans = Math.max(ans, itm);
             
            // Traversing the Hashmap from reverse
            for (; ans > 0; ans--) {
                if (!(ans in m))
                    break;
            }
            return ans;
        }
 
        // Driver code
        let arr = [2, 3, 7, 6, 8];
        let missing = firstMissingPositive(arr) == 0
            ? -1
            : firstMissingPositive(arr);
        document.write(missing);
 
    // This code is contributed by rakeshsahni
 
    </script>

5

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)