Encuentre el número positivo más pequeño que falta en una array desordenada | conjunto 3

Dada una array desordenada con elementos positivos y negativos. La tarea es encontrar el número positivo más pequeño que falta en la array.

Ejemplos: 

Entrada: arr[] = {2, 3, 7, 6, 8, -1, -10, 15} 
Salida: 1

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

Entrada: arr[] = {1, 1, 0, -1, -2} 
Salida: 2 

Enfoque: 
Ya hemos discutido algunas de las técnicas para encontrar el número positivo más pequeño que falta en una array no ordenada.
Encuentre el número positivo más pequeño que falta en una array desordenada | Conjunto 1  
Encuentra el número positivo más pequeño que falta en una array desordenada | Set 2
Aquí, usamos set para almacenar todos los enteros positivos y encontrar el primer entero positivo faltante. 

// CPP program to find the smallest
// positive missing number
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the smallest
// positive missing number
int findMissingPositive(int arr[], int n)
{
    // Default smallest Positive Integer
    int m = 1;
 
    // Store values in set which are
    // greater than variable m
    set<int> x;
 
    for (int i = 0; i < n; i++) {
        // Store value when m is less than
        // current index of given array
        if (m < arr[i]) {
            x.insert(arr[i]);
        }
        else if (m == arr[i]) {
            // Increment m when it is equal
            // to current element
            m = m + 1;
 
            while (x.count(m)) {
                x.erase(m);
 
                // Increment m when it is one of the
                // element of the set
                m = m + 1;
            }
        }
    }
 
    // Return the required answer
    return m;
}
 
// Driver code
int main()
{
    int arr[] = { 2, 3, -7, 6, 8, 1, -10, 15 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    cout << findMissingPositive(arr, n);
 
    return 0;
}

// Java program to find the smallest
// positive missing number
import java.util.*;
 
class GFG
{
 
// Function to find the smallest
// positive missing number
static int findMissingPositive(int arr[], int n)
{
    // Default smallest Positive Integer
    int m = 1;
 
    // Store values in set which are
    // greater than variable m
    HashSet<Integer> x = new HashSet<Integer>();
 
    for (int i = 0; i < n; i++)
    {
        // Store value when m is less than
        // current index of given array
        if (m < arr[i])
        {
            x.add(arr[i]);
        }
        else if (m == arr[i])
        {
            // Increment m when it is equal
            // to current element
            m = m + 1;
 
            while (x.contains(m))
            {
                x.remove(m);
 
                // Increment m when it is one of the
                // element of the set
                m = m + 1;
            }
        }
    }
 
    // Return the required answer
    return m;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 2, 3, -7, 6, 8, 1, -10, 15 };
 
    int n = arr.length;
 
    // Function call
    System.out.println(findMissingPositive(arr, n));
}
}
 
// This code is contributed by 29AjayKumar

# Python 3 program to find the smallest
# positive missing number
 
# Function to find the smallest
# positive missing number
def findMissingPositive(arr, n):
     
    # Default smallest Positive Integer
    m = 1
 
    # Store values in set which are
    # greater than variable m
    x = []
    for i in range(n):
         
        # Store value when m is less than
        # current index of given array
        if (m < arr[i]):
            x.append(arr[i])
     
        elif (m == arr[i]):
             
            # Increment m when it is equal
            # to current element
            m = m + 1
 
            while (x.count(m)):
                x.remove(m)
 
                # Increment m when it is one of the
                # element of the set
                m = m + 1
 
    # Return the required answer
    return m
 
# Driver code
if __name__ == '__main__':
    arr = [2, 3, -7, 6, 8, 1, -10, 15]
 
    n = len(arr)
 
    # Function call
    print(findMissingPositive(arr, n))
 
# This code is contributed by
# Surendra_Gangwar

// C# program to find the smallest
// positive missing number
using System;
using System.Collections.Generic;
     
class GFG
{
 
// Function to find the smallest
// positive missing number
static int findMissingPositive(int []arr, int n)
{
    // Default smallest Positive Integer
    int m = 1;
 
    // Store values in set which are
    // greater than variable m
    HashSet<int> x = new HashSet<int>();
 
    for (int i = 0; i < n; i++)
    {
        // Store value when m is less than
        // current index of given array
        if (m < arr[i])
        {
            x.Add(arr[i]);
        }
         
        else if (m == arr[i])
        {
            // Increment m when it is equal
            // to current element
            m = m + 1;
 
            while (x.Contains(m))
            {
                x.Remove(m);
 
                // Increment m when it is one of the
                // element of the set
                m = m + 1;
            }
        }
    }
 
    // Return the required answer
    return m;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 2, 3, -7, 6, 8, 1, -10, 15 };
 
    int n = arr.Length;
 
    // Function call
    Console.WriteLine(findMissingPositive(arr, n));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript program to find the smallest
// positive missing number
 
// Function to find the smallest
// positive missing number
function findMissingPositive(arr, n)
{
    // Default smallest Positive integer
    let m = 1;
 
    // Store values in set which are
    // greater than variable m
    let x = new Set();
 
    for (let i = 0; i < n; i++) {
        // Store value when m is less than
        // current index of given array
        if (m < arr[i]) {
            x.add(arr[i]);
        }
        else if (m == arr[i]) {
            // Increment m when it is equal
            // to current element
            m = m + 1;
 
            while (x.has(m)) {
                x.delete(m);
 
                // Increment m when it is one of the
                // element of the set
                m = m + 1;
            }
        }
    }
 
    // Return the required answer
    return m;
}
 
// Driver code
 
let arr = [2, 3, -7, 6, 8, 1, -10, 15];
 
let n = arr.length;
 
// Function call
document.write(findMissingPositive(arr, n));
 
 
// This code is contributed by _saurabh_jaiswal
 
</script>

4

Complejidad del tiempo: O(nlog(n))

Espacio Auxiliar: O(n)