QN; Aquí está la pregunta. No sé dónde está mal mi algoritmo. Ayúdame a encontrar pls

Dado un conjunto A de longitud N. Necesitamos calcular el siguiente elemento mayor para cada elemento en una matriz dada. Si el siguiente elemento mayor no está disponible en una matriz dada, entonces necesitamos completar ‘_ 'en ese lugar del índice.

Entrada: La primera línea contiene un número entero T, el número de casos de prueba. Para cada caso de prueba, la primera línea contiene un número entero n, el tamaño de la matriz. La siguiente línea contiene n enteros separados por espacios que denotan los elementos de la matriz.

Salida: para cada caso de prueba, la salida es una matriz que muestra el siguiente elemento mayor a elemento en ese índice.

Constraints:
1 <= T <= 100
1 <= N <= 100
-106 <= Ai <= 106

Example:
Input
2
9
6 3 9 8 10 2 1 15 7
4
13 6 7 12

Output:
7 6 10 9 15 3 2 _ 8
_ 7 12 13

Explicación: Caso de prueba 1: Aquí cada elemento de la matriz tiene el siguiente elemento mayor, pero en el índice 7, 15 es el elemento más grande de la matriz dada y ningún otro elemento es mayor de 15, por lo que en el índice de 15 lo llenamos con ''. Caso de prueba 2: Aquí, en el índice 0, 13 es el mayor valor en una matriz dada y ningún otro elemento de matriz es mayor que 13, por lo que en el índice 0 llenamos ''.

Mi solución:

//NOT SOLVED YET
#include<iostream>
using namespace std;
int main()
{
    int a[10]={6 ,3 ,9, 8 ,10, 2 ,1, 15, 7};
    int b[10],flag=0,big=-1,i,j;
    for(i=0;i<10;i++)
    {
        for(j=0;j<10;j++)
        {
            if(i==j)continue;
            if((a[j]>a[i]) && (flag==0))
            {
                big=a[j];
                flag=1;
            }
            else if(a[j]<big && big>a[i] && flag==1)
                big=a[j];

        }
        if(big==-1)cout<<'_';
        else cout<<big<<' ';
        big=-1;
        flag=0;
    }

}

La salida que obtengo es:

 2 2 2 2 7 1 0 _ 2 1
-1
rishi_harshan 15 feb. 2020 a las 21:44

2 respuestas

La mejor respuesta

La condición debe ser:

    else if(a[j] < big && a[j] > a[i] && flag == 1)

De hecho, si usa big > a[i], eso significa que simplemente verifica si el elemento por lo tanto mucho más grande era mayor que a[i], pero esto permite seleccionar un valor más adelante en el proceso que es más pequeño que big, pero también más pequeño que a[i]. Aquí, por lo tanto, queremos comprobar si a[j] está entre a[i] y big.

Dicho esto, el enfoque anterior no es muy eficiente. De hecho, para cada elemento, calcula el siguiente elemento en tiempo lineal , lo que lo convierte en un algoritmo de tiempo cuadrático . Es posible que desee buscar soluciones donde la lista se ordena primero. Puede, por ejemplo, usar min-heap aquí para moverse por la lista en dos pasadas.

2
Willem Van Onsem 15 feb. 2020 a las 20:05

Para ampliar lo que otros han mencionado, que actualmente tiene un algoritmo O (N ^ 2), y esto se puede hacer de manera más eficiente.

No creo que pueda obtener O (N) aquí, pero aquí hay un plan para un algoritmo O (N log N):

Para cada caso de prueba:

  • Cargue los valores de Ai en dos matrices, llamémoslos X e Y
  • Ordenar la matriz Y
  • Itere sobre X y para cada elemento de X haga una búsqueda binaria en Y para encontrar el siguiente valor más grande de Ai: use eso como salida, o use _ si no encontró uno

Recomiendo, para fines prácticos, implementar esto usando la biblioteca estándar de C ++, usando https: / /en.cppreference.com/w/cpp/algorithm/sort y https : //en.cppreference.com/w/cpp/algorithm/upper_bound, e implementando las dos funciones anteriores usted mismo, consulte: https://en.wikipedia.org/wiki/Quicksort

1
DeducibleSteak 15 feb. 2020 a las 19:13