Encuentre la array Prefijo-MEX para la array dada

Dada una array A[] de N elementos, la tarea es crear una array Prefix-MEX para esta array dada. La array Prefix-MEX B[] de una array A[] se crea de tal manera que MEX de A[0] hasta que A[i] es B[i] . 

MEX de una array se refiere al entero no negativo faltante más pequeño de la array.

Ejemplos:

Entrada : A[] = {1, 0, 2, 4, 3}
Salida : 0 2 3 3 5
Explicación: En la array A, los elementos 
hasta el 1er índice, los elementos son [1] y mex hasta el 1er índice es 0.
Hasta 2do índice, los elementos son [1, 0] y mex hasta el 2do índice es 2.
Hasta el 3er índice, los elementos son [1, 0, 2] y mex hasta el 3er índice es 3.
Hasta el 4to índice, los elementos son [1, 0, 2, 4] y mex hasta el 4.° índice es 3.
Hasta el 5.° índice, los elementos son [1, 0, 2, 4, 3] y mex hasta el 5.° índice es 5.
Entonces, nuestra array final B sería [0, 2, 3 , 3, 5].

Entrada : A[] = [1, 2, 0]
Salida : [0, 0, 3]
Explicación: En la array A, los elementos 
hasta el 1er índice, los elementos son [1] y mex hasta el 1er índice es 0.
Hasta el 2do índice , los elementos son [1, 2] y mex hasta el 2.º índice es 0.
Hasta el 3.er índice, los elementos son [1, 2, 0] y mex hasta el 3.er índice es 3.
Por lo tanto, nuestra array final B sería [0, 0, 3 ].

Enfoque ingenuo: la forma más sencilla de resolver el problema es:

Para cada elemento en el índice i ^th (0 ≤ i < N) de la array A[] , encuentre MEX de 0 a i y guárdelo en B[i] .

Siga los pasos mencionados a continuación para implementar la idea:

• Iterar sobre la array de i = 0 a N-1 :
  • Para cada i ^-ésimo índice en el arreglo A[] : 
    • Ejecute un ciclo for para encontrar el MEX del índice 0 hasta i .
    • Luego almacene este MEX en el índice i en la array resultante B[i] .
• Devuelve la array resultante B[] al final.

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)

Enfoque eficiente: este enfoque se basa en el uso de la estructura de datos establecida .

Un conjunto almacena datos en orden ordenado. Podemos aprovechar eso y almacenar todos los enteros no negativos hasta el valor máximo de la array. Luego recorra cada elemento de la array y elimine los datos visitados del conjunto. El elemento restante más pequeño será el MEX para ese índice.

Siga los pasos a continuación para implementar la idea:

• Encuentre el elemento máximo de la array A[] .
• Cree un conjunto y almacene los números desde 0 hasta el elemento máximo en el conjunto.
• Atraviesa la array desde i = 0 hasta N-1 : 
  • Para cada elemento, borre ese elemento del conjunto.
  • Ahora encuentre el elemento más pequeño que queda en el conjunto.
  • Este es el prefijo MEX para el i ^-ésimo elemento. Almacene este valor en la array resultante.
• Devuelve la array resultante como la respuesta requerida.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to fint the prefix MEX
// for each array element
vector<int> Prefix_Mex(vector<int>& A, int n)
{
    // Maximum element in vector A
    int mx_element = *max_element(A.begin(), A.end());
 
    // Store all number from 0
    // to maximum element + 1 in a set
    set<int> s;
    for (int i = 0; i <= mx_element + 1; i++) {
        s.insert(i);
    }
 
    // Loop to calculate Mex for each index
    vector<int> B(n);
    for (int i = 0; i < n; i++) {
 
        // Checking if A[i] is present in set
        auto it = s.find(A[i]);
 
        // If present then we erase that element
        if (it != s.end())
            s.erase(it);
 
        // Store the first element of set
        // in vector B as Mex of prefix vector
        B[i] = *s.begin();
    }
 
    // Return the vector B
    return B;
}
 
// Driver code
int main()
{
 
    vector<int> A = { 1, 0, 2, 4, 3 };
    int N = A.size();
 
    // Function call
    vector<int> B = Prefix_Mex(A, N);
 
    // Print the prefix MEX array
    for (int i = 0; i < N; i++) {
        cout << B[i] << " ";
    }
    return 0;
}

// Java code to implement the approach
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.stream.Collectors;
 
class GFG{
 
// Function to fint the prefix MEX
// for each array element
static int[] Prefix_Mex(int[] A, int n)
{
   
    // Maximum element in vector A
    int mx_element = Arrays.stream(A).max().getAsInt();
 
    // Store all number from 0
    // to maximum element + 1 in a set
    LinkedHashSet<Integer> s = new LinkedHashSet<>();
    for (int i = 0; i <= mx_element + 1; i++) {
        s.add(i);
    }
 
    // Loop to calculate Mex for each index
    int []B = new int[n];
    for (int i = 0; i < n; i++) {
 
        // Checking if A[i] is present in set
        // If present then we erase that element
        if (s.contains(A[i]))
            s.remove(A[i]);
 
        // Store the first element of set
        // in vector B as Mex of prefix vector
        B[i] = s.stream().collect(Collectors.toList()).get(0);
    }
 
    // Return the vector B
    return B;
}
 
// Driver code
public static void main(String[] args)
{
 
    int[] A = { 1, 0, 2, 4, 3 };
    int N = A.length;
 
    // Function call
    int[] B = Prefix_Mex(A, N);
 
    // Print the prefix MEX array
    for (int i = 0; i < N; i++) {
        System.out.print(B[i]+ " ");
    }
}
}
 
// This code is contributed by shikhasingrajput

# Python code to implement the approach
 
# Function to fint the prefix MEX
# for each array element
def Prefix_Mex(A, n):
    # Maximum element in vector A
    mx_element = max(A)
    # Store all number from 0
    # to maximum element + 1 in a set
    s = {}
    for i in range(mx_element+2):
        s[i] = True
 
    # Loop to calculate Mex for each index
    B = [0]*n
    for i in range(n):
        # Checking if A[i] is present in set
        # If present then we erase that element
        if A[i] in s.keys():
            del s[A[i]]
        # Store the first element of set
        # in vector B as Mex of prefix vector
        B[i] = int(list(s.keys())[0])
        # Return the list B
    return B
 
 
# Driver code
if __name__ == "__main__":
    A = [1, 0, 2, 4, 3]
    N = len(A)
 
    # Function call
    B = Prefix_Mex(A, N)
 
    # Print the prefix MEX array
    for i in range(N):
        print(B[i], end=" ")
 
# This code is contributed by Rohit Pradhan

<script>
        // JavaScript code to implement the approach
 
        // Function to fint the prefix MEX
        // for each array element
        const Prefix_Mex = (A, n) => {
            // Maximum element in vector A
            let mx_element = Math.max(...A);
 
            // Store all number from 0
            // to maximum element + 1 in a set
            let s = new Set();
 
            for (let i = 0; i <= mx_element + 1; i++) {
                s.add(i);
            }
 
            // Loop to calculate Mex for each index
            let B = new Array(n).fill(0);
            for (let i = 0; i < n; i++) {
 
                // Checking if A[i] is present in set
                let it = s.has(A[i]);
 
                // If present then we erase that element
                if (it) s.delete(A[i]);
 
 
                // Store the first element of set
                // in vector B as Mex of prefix vector
                B[i] = s.values().next().value;
            }
 
            // Return the vector B
            return B;
        }
 
        // Driver code
 
        let A = [1, 0, 2, 4, 3];
        let N = A.length;
 
        // Function call
        let B = Prefix_Mex(A, N);
 
        // Print the prefix MEX array
        for (let i = 0; i < N; i++) {
            document.write(`${B[i]} `);
        }
 
        // This code is contributed by rakeshsahni
 
    </script>

0 2 3 3 5 

Complejidad de tiempo: O(N * log N )

• O(N) para iterar el vector, y 
• O(log N) para insertar y eliminar el elemento del conjunto.

Espacio Auxiliar: O(N)