Saltar al contenido

La subsecuencia lexicográficamente más pequeña de Array eliminando todas las copias de un elemento

Dada una matriz A[] de norte enteros, la tarea es encontrar la subserie lexicográficamente más pequeña de la matriz dividiendo todas las ocurrencias de precisamente un entero de la matriz.

Ejemplos:

Aporte: n = 5, un[] = {2, 4, 4, 1, 3}
Salida: {2, 1, 3}
Explicación: Todas las subcadenas posibles de la matriz
después de eliminar exactamente un entero son:
Al borrar 2: {4, 4, 1, 3}
Al quitar 4: {2, 1, 3}
Al quitar 1: {2, 4, 4, 3}
Al eliminar 3: {2, 4, 4, 1}
Lexicográficamente el más pequeño de estos es {2, 1, 3}

Aporte: n = 6, un[] = {1, 1, 1, 1, 1, 1}
Salida: {}

Acercarse: Siga la observación a continuación para resolver el problema:

observación:

Se puede observar fácilmente que para hacer que una subcadena de una matriz sea lexicográficamente más pequeña, se debe eliminar el primer elemento que sea más grande que el siguiente.

Con base en la observación anterior, se pueden seguir los siguientes pasos para llegar a la solución:

  • Ciclo a través de la matriz.
  • En cada iteración, compare el elemento actual con el elemento siguiente.
  • Si es mayor que el siguiente elemento, rompa el bucle y elimine todas las instancias del elemento actual.
  • De lo contrario, si la iteración se completa sin interrumpir el ciclo, significa que la matriz se ordena en orden ascendente. En ese caso, elimine todas las instancias del último elemento de la matriz.

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

C++

 

#include <bits/stdc++.h>

using namespace std;

 

void printSmallestSubsequence(int N, int A[])

{

 

    

    

    int target = A[N - 1];

 

    

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

 

        

        

        

        

        if (A[i] > A[i + 1]) {

            target = A[i];

            break;

        }

    }

 

    

    

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

        if (A[i] != target) {

            cout << A[i] << " ";

        }

    }

}

 

int main()

{

    int N = 5;

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

 

    

    printSmallestSubsequence(N, A);

    return 0;

}

Complejidad del tiempo: A)
cuarto auxiliar: O(1)