Saltar al contenido

Encuentre la matriz Prefix-MEX para una matriz dada

Dada una matriz A[] de norte elementos, la tarea es Prefijo-MEX matriz para esta matriz dada. Matriz de prefijo-MEX B[] de una matriz A[] está hecho de tal manera que MEX de A[0] a A[i] es B[i]†

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

Ejemplos:

Aporte: A[] = {1, 0, 2, 4, 3}
Salida:: 0 2 3 3 5
Explicación: En la matriz A, los elementos
Hasta el 1er índice, los elementos son [1] y mex al 1er índice es 0.
Hasta el 2do índice, los elementos son [1, 0] y mex al segundo índice es 2.
Hasta el 3er índice, los elementos son [ 1, 0, 2] y mex al tercer índice es 3.
Hasta el 4º índice, los elementos son [ 1, 0, 2, 4] y mex al cuarto índice es 3.
Hasta el índice 5, los elementos son [ 1, 0, 2, 4, 3] y mex al quinto índice es 5.
Entonces nuestra última matriz sería B [0, 2, 3, 3, 5]†

Aporte: A[] † [ 1, 2, 0 ]
Salida:† [ 0, 0, 3 ]
Explicación: En la matriz A, los elementos
Hasta el 1er índice, los elementos son [1] y mex al 1er índice es 0.
Hasta el 2do índice, los elementos son [1, 2] y mex al segundo índice es 0.
Hasta el 3er índice, los elementos son [ 1, 2, 0] y mex al tercer índice es 3.
Entonces nuestra última matriz sería B [0, 0, 3]†

Enfoque ingenuo: La forma más fácil de resolver el problema es:

Para cada elemento en imi (0 ≤ i < N)índice de la matriz A[]encontrar MEX de 0 a yo y guárdalo B[i]†

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

  • Repita la matriz de Yo = 0 a N-1†
    • Para cada imi índice en matriz A[]†
  • Devolver la matriz resultante B[] al final.

Complejidad del tiempo: A2†
cuarto auxiliar: A)

Enfoque eficiente: Este enfoque se basa en el uso de la estructura de datos Set.

Un conjunto almacena datos en orden ordenado. Podemos aprovechar esto y almacenar todos los enteros no negativos hasta el valor máximo de la matriz. Luego itere a través de cada elemento de la matriz y elimine los datos visitados del conjunto. El elemento más pequeño que queda es el MEX para ese índice.

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

  • Encuentre el elemento máximo de la matriz A[]†
  • Haz un set y guarda las canciones de 0 hasta el elemento máximo del conjunto.
  • Recorra la matriz de Yo = 0 a N-1†
    • Para cada elemento, elimine ese elemento del conjunto.
    • Ahora encuentre el elemento más pequeño que queda en el conjunto.
    • Este es el prefijo MEX para el imi elemento. Almacene este valor en la matriz resultante.
  • Devuelve la matriz resultante como la respuesta requerida.

A continuación encontrará la implementación del enfoque anterior.

C++

 

#include <bits/stdc++.h>

using namespace std;

 

vector<int> Prefix_Mex(vector<int>& A, int n)

{

    

    int mx_element = *max_element(A.begin(), A.end());

 

    

    

    set<int> s;

    for (int i = 0; i <= mx_element + 1; i++) {

        s.insert(i);

    }

 

    

    vector<int> B(n);

    for (int i = 0; i < n; i++) {

 

        

        auto it = s.find(A[i]);

 

        

        if (it != s.end())

            s.erase(it);

 

        

        

        B[i] = *s.begin();

    }

 

    

    return B;

}

 

int main()

{

 

    vector<int> A = { 1, 0, 2, 4, 3 };

    int N = A.size();

 

    

    vector<int> B = Prefix_Mex(A, N);

 

    

    for (int i = 0; i < N; i++) {

        cout << B[i] << " ";

    }

    return 0;

}

Complejidad del tiempo: O(N * registro N )

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

cuarto auxiliar: A)