Saltar al contenido

Sustituciones mínimas con 0 para ordenar la matriz

Dada una matriz A[] de norte enteros, la tarea es encontrar el número mínimo de operaciones para ordenar la matriz en orden no descendente, eligiendo un número entero X y reemplazando todas las copias de X en la matriz con 0.

Ejemplos:

Aporte: n = 5, un[] = {2, 2, 1, 1, 3}
Salida: 1
Explicación: Elegimos X = 2 y reemplazamos todas las ocurrencias de 2 con 0. Ahora la matriz {2, 21, 1, 3} -> {0, 01, 1, 3} , que se ordena en orden ascendente.

Aporte: n = 4, un[] = {2, 4, 1, 2}
Salida: 3

Acercarse: El problema se puede resolver fácilmente usando un mapa.

observaciones:

Hay 2 casos a considerar:

  • Caso 1: El mismo elemento aparece más de una vez no contiguo
    • Considere la matriz: {1,6,3,4,5,3,2}.
    • Dado que 3 en el índice 5 es mayor que el siguiente elemento, lo convertimos en 0 (al igual que 3 en el índice 2).
    • La matriz se convierte en {1,6,0,4.5,0,2}.
    • Entonces, la única forma de ordenar la matriz sería hacer que todos los elementos antes de los ceros sean iguales a 0. Es decir, la matriz se convierte en {0.0,0.0,0.0,2}.
  • Caso 2: El elemento del índice es más grande que el elemento del índice (i+1):
    • Considere la matriz: {1,2,3,5,4}.
    • Dado que el elemento del tercer índice es mayor que el elemento del cuarto índice, debemos hacer que el elemento del tercer índice sea igual a cero.
    • Entonces la matriz se convierte en {1,2,3,0,4}.
    • La única forma de ordenar la matriz sería hacer que todos los elementos antes del cero sean iguales a 0. Es decir, la matriz se convierte en {0.0,0.0,4}.

Se puede notar que el Caso 2 eventualmente se descompone en el Caso 1.

Teniendo en cuenta los casos anteriores, el problema se puede resolver siguiendo los pasos a continuación:

  • Declare un mapa hash y agregue la frecuencia de cada elemento de la matriz al mapa.
  • Recorra la matriz desde atrás, es decir, desde i=N-1 hasta i=0.
  • Con cada iteración, maneje los Casos 1 y 2 como se explicó anteriormente.
  • Cuando se completa la iteración, devuelve 0.

A continuación se muestra la implementación de este enfoque:

C++

#include <bits/stdc++.h>

using namespace std;

 

int minimumReplacements(int A[], int N)

{

    

    map<int, int> mp;

 

    

    

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

        mp[A[i]]++;

    }

 

    

    for (int i = N - 1; i >= 0; i--) {

 

        

        

        while (i > 0 && A[i] == A[i - 1]) {

            mp[A[i]]--;

            i--;

        }

 

        mp[A[i]]--;

 

        

        

        if (mp[A[i]] == 0) {

            mp.erase(A[i]);

        }

 

        

        if (mp.find(A[i]) != mp.end()) {

            return mp.size();

        }

 

        

        if (i > 0 && A[i - 1] > A[i]) {

            return mp.size();

        }

    }

 

    

    

    return 0;

}

 

int main()

{

    int N = 5;

    int A[] = { 2, 2, 1, 1, 3 };

 

    

    int answer = minimumReplacements(A, N);

    cout << answer;

}

Complejidad del tiempo: A)
cuarto auxiliar: A)