3 Dada una serie de elementos distintos, imprima el elemento mayor más cercano para cada elemento. El elemento mayor más cercano a un elemento x es el elemento más pequeño del lado derecho de x en la array que es mayor que x. Elementos para los que no existe un elemento mayor, considere el siguiente elemento mayor como -1.
Ejemplos:
Input: arr[] = {4, 5, 2, 25}
Output:
Element NGE
4 --> 5
5 --> 25
2 --> 25
25 --> -1
Input: arr[] = {4, 10, 7}
Output:
Element NGE
4 --> 7
10 --> -1
7 --> -1
Enfoque: en esta publicación, discutiremos cómo encontrar el siguiente elemento mayor usando C++ STL( set ).
Encontrar el elemento mayor más pequeño en el lado derecho será como encontrar el primer elemento mayor del elemento actual en una lista ordenada.
Considere el ejemplo 1, la lista ordenada se vería como 2, 4, 5, 25.
Aquí, para el elemento 4, el elemento mayor es 5 ya que está junto a él, por lo que imprimimos 5 y eliminamos 4 porque no sería mayor que el otros elementos ya que ya no está a la derecha de nadie.
Del mismo modo, para 5 es 25 y eliminamos 5 de la lista, ya que 5 no estará a la derecha de 2 o 25, por lo que se puede eliminar.
A continuación se detallan los pasos para encontrar el siguiente elemento mayor de cada elemento del índice.
- Inserte todos los elementos en un Conjunto , almacenará todos los elementos en orden creciente.
- Iterar en la array de elementos y, para cada índice, encontrar el límite superior del elemento de índice actual. upper_bound() devuelve un iterador que puede apuntar a la siguiente posición.
- Si el iterador apunta a una posición más allá del último elemento, entonces no existe NGE para el elemento de índice actual.
- Si el iterador apunta a una posición que hace referencia a un elemento, ese elemento es el NGE del elemento de índice actual.
- Encuentre la posición del elemento de índice actual en cada recorrido y elimínelo del conjunto usando las funciones >lower_bound() y erase() del conjunto.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to print the
// NGE's of array elements using
// C++ STL
#include <bits/stdc++.h>
using namespace std;
// Function to print the NGE
void printNGE(int a[], int n)
{
set<int> ms;
// insert in the multiset container
for (int i = 0; i < n; i++)
ms.insert(a[i]);
cout << "Element "
<< "NGE";
// traverse for all array elements
for (int i = 0; i < n; i++) {
// find the upper_bound in set
auto it = ms.upper_bound(a[i]);
// if points to the end, then
// no NGE of that element
if (it == ms.end()) {
cout << "\n " << a[i]
<< " ----> " << -1;
}
// print the element at that position
else {
cout << "\n " << a[i]
<< " ----> " << *it;
}
// find the first occurrence of
// the index element and delete it
it = ms.lower_bound(a[i]);
// delete one occurrence
// from the container
ms.erase(it);
}
}
// Driver Code
int main()
{
int a[] = { 4, 5, 2, 25 };
int n = sizeof(a) / sizeof(a[0]);
// Function call to print the NGE
printNGE(a, n);
return 0;
}
Java
// C++ program to print the
// NGE's of array elements using
import java.util.TreeSet;
class Geeks {
// Function to print the NGE
static void printNGE(int[] a, int n)
{
// Tree Set is an ordered set used to
// store elements in a sorted manner
TreeSet<Integer> t = new TreeSet<>();
// Adding elements into the set
for (int i = 0; i < n; i++)
t.add(a[i]);
System.out.println("ELEMENT NGE");
for (int i = 0; i < n; i++) {
// If the elements does not have an upper bound
// or an element greater than it,
// higher method of TreeSet class will return NULL
if (t.higher(a[i]) == null)
System.out.println(a[i] + " ----> "
+ "-1");
// Otherwise print the upper bound of that element
else
System.out.println(a[i] + " ----> " + t.higher(a[i]));
// Remove the current element from the set
t.remove(a[i]);
}
}
// Driver code
public static void main(String[] args)
{
int a[] = { 4, 5, 2, 25 };
int n = a.length;
printNGE(a, n);
}
}
Python3
# Python3 program to print the
# NGE's of array elements
from bisect import bisect_right as upper_bound, \
bisect_left as lower_bound
# Function to print the NGE
def printNGE(a: list, n):
ms = set()
# insert in the multiset container
for i in range(n):
ms.add(a[i])
print("Element NGE", end = "")
# Required because Python sets
# are not sorted
new_arr = list(ms)
new_arr.sort()
# traverse for all array elements
for i in range(n):
# find the upper_bound in set
it = upper_bound(new_arr, a[i])
# if points to the end, then
# no NGE of that element
if (it == len(new_arr)):
print("\n %d ----> -1" % a[i], end = "")
# print the element at that position
else:
print("\n %d ----> %d" % (a[i],
new_arr[it]), end = "")
# find the first occurrence of
# the index element and delete it
it = lower_bound(new_arr, a[i])
# delete one occurrence
# from the container
new_arr.remove(new_arr[it])
# Driver Code
if __name__ == "__main__":
a = [4, 5, 2, 25]
n = len(a)
# Function call to print the NGE
printNGE(a, n)
# This code is contributed by
# sanjeev2552
Javascript
<script>
// Javascript program to print the
// NGE's of array elements using
// Function to print the NGE
function printNGE(a , n) {
// Tree Set is an ordered set used to
// store elements in a sorted manner
var t = new Set();
// Adding elements into the set
for (var i = 0; i < n; i++)
t.add(a[i]);
document.write("ELEMENT NGE<br/>");
for (i = 0; i < n; i++) {
// If the elements does not have an upper bound
// or an element greater than it,
// higher method of TreeSet class will return NULL
if (upper_bound(t,a[i]) == null)
document.write(a[i] + " ----> " + "-1"+"<br/>");
// Otherwise print the upper bound of that element
else
document.write(a[i] + " ----> " + upper_bound(t,a[i])+"<br/>");
// Remove the current element from the set
t.delete(a[i]);
}
}
function upper_bound(s, val)
{
let temp = [...s];
temp.sort((a, b) => b - a);
return temp[temp.indexOf(val) + 1];
}
// Driver code
var a = [ 4, 5, 2, 25 ];
var n = a.length;
printNGE(a, n);
// This code contributed by Rajput-Ji
</script>
Element NGE 4 ----> 5 5 ----> 25 2 ----> 25 25 ----> -1
Complejidad de tiempo : O (N * logN), ya que estamos usando un bucle para atravesar N veces y en cada recorrido estamos insertando en el conjunto que nos costará logN tiempo.
Espacio auxiliar : O (N), ya que estamos usando espacio adicional para establecer ms .