array desordenado, encontrar el siguiente elemento más grande para cada elemento, de lo contrario imprimir -1
El requisito es un poco complicado. Supongamos que tenemos un array desordenado, por ejemplo: {12, 72, 93, 0, 24, 56, 102}.
Si tenemos una posición impar, debemos buscar el siguiente elemento mayor en su derecha. Por ejemplo, tomemos v[1] = 12, el siguiente elemento mayor para ’12’ es 24.
Pero si tenemos una posición par, debemos buscar el siguiente elemento mayor en su izquierda. Por ejemplo, tomemos v[2] = 72, no hay ningún número que sea mayor que ’72’, por lo que mostraremos ‘-1’. Tomemos otro ejemplo, v[4] = 0, el siguiente elemento mayor para ‘0’ es 12.
La salida debería ser: 24 -1 102 12 56 72 -1.
Intenté resolver esto en c++:
#include <iostream>
using namespace std;
int main() {
const int CONST = 10000;
int n, v[CONST];
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
for (int i = 1; i <= n; i++) {
int next = -1;
if (i % 2 != 0) {
for (int j = i + 1; j <= n; j++) {
if (v[j] > v[i]) {
next = v[j];
break;
}
}
cout << next << " ";
}
else {
for (int k = 1; k <= i - 1; k++) {
if (v[k] > v[i]) {
next = v[k];
break;
}
}
cout << next << " ";
}
}
return 0;
}
En primer lugar, pienso que debo ordenar el array y después usar búsqueda binaria para encontrar el siguiente elemento mayor.
davy.ai
Como experto en TI especializado en C++, el problema dado se puede resolver sin ordenar el array utilizando dos bucles para iterar a través del array dado. El primer bucle iterará a través de cada elemento del array y el segundo bucle buscará el próximo elemento mayor basado en las condiciones proporcionadas en el problema.
Aquí está el código actualizado:
“`c++
#include
#include
using namespace std;
int main() { v, ans;
int n, temp;
vector
cin >> n;
for (int i = 0; i < n; i++) {
cin >> temp;
v.push_back(temp);
}
for (int i = 0; i < n; i++) {
int next = -1;
if (i % 2 != 0) {
for (int j = i + 1; j < n; j++) {
if (v[j] > v[i]) {
next = v[j];
break;
}
}
}
else {
for (int k = i – 1; k >= 0; k–) {
if (v[k] > v[i]) {
next = v[k];
break;
}
}
}
ans.push_back(next);
}
for (int i = 0; i < n; i++) {
cout << ans[i] << ” “;
}
return 0;
}
“`
En el código actualizado, hemos utilizado un vector para almacenar el array de entrada, el vector de solución y para iterar a través de ellos. En el primer bucle, almacenamos cada elemento del array de entrada y en el segundo bucle, buscamos el próximo elemento mayor basado en si el índice es impar o par. Si el índice es impar, buscamos el elemento solo a la derecha de él y si el índice es par, buscamos el elemento solo a la izquierda de él. Finalmente, almacenamos la solución en un vector y lo imprimimos.
La complejidad temporal del código anterior es O(n^2) ya que tenemos dos bucles. Sin embargo, esto es óptimo ya que necesitamos verificar cada elemento del array para satisfacer las condiciones dadas.