Dada una array de enteros, reemplace cada elemento con el elemento menor mayor en su lado derecho en la array. Si no hay elementos mayores en el lado derecho, reemplácelo con -1.
Ejemplos:
Input: [8, 58, 71, 18, 31, 32, 63, 92,
43, 3, 91, 93, 25, 80, 28]
Output: [18, 63, 80, 25, 32, 43, 80, 93,
80, 25, 93, -1, 28, -1, -1]
Un método ingenuo es ejecutar dos bucles. El bucle exterior seleccionará uno por uno los elementos de la array de izquierda a derecha. El bucle interior encontrará el elemento más pequeño mayor que el elemento seleccionado en su lado derecho. Finalmente, el bucle externo reemplazará el elemento seleccionado con el elemento encontrado por el bucle interno. La complejidad temporal de este método será O(n 2 ).
Una solución complicada sería usar árboles de búsqueda binarios. Comenzamos a escanear la array de derecha a izquierda e insertamos cada elemento en el BST. Para cada elemento insertado, lo reemplazamos en la array por su sucesor en orden en BST. Si el elemento insertado es el máximo hasta el momento (es decir, su sucesor en orden no existe), lo reemplazamos por -1.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to replace every element with the
// least greater element on its right
#include <bits/stdc++.h>
using namespace std;
// A binary Tree node
struct Node {
int data;
Node *left, *right;
};
// A utility function to create a new BST node
Node* newNode(int item)
{
Node* temp = new Node;
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
/* A utility function to insert a new node with
given data in BST and find its successor */
Node* insert(Node* node, int data, Node*& succ)
{
/* If the tree is empty, return a new node */
if (node == NULL)
return node = newNode(data);
// If key is smaller than root's key, go to left
// subtree and set successor as current node
if (data < node->data) {
succ = node;
node->left = insert(node->left, data, succ);
}
// go to right subtree
else if (data > node->data)
node->right = insert(node->right, data, succ);
return node;
}
// Function to replace every element with the
// least greater element on its right
void replace(int arr[], int n)
{
Node* root = NULL;
// start from right to left
for (int i = n - 1; i >= 0; i--) {
Node* succ = NULL;
// insert current element into BST and
// find its inorder successor
root = insert(root, arr[i], succ);
// replace element by its inorder
// successor in BST
if (succ)
arr[i] = succ->data;
else // No inorder successor
arr[i] = -1;
}
}
// Driver Program to test above functions
int main()
{
int arr[] = { 8, 58, 71, 18, 31, 32, 63, 92,
43, 3, 91, 93, 25, 80, 28 };
int n = sizeof(arr) / sizeof(arr[0]);
replace(arr, n);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Java
// Java program to replace every element with
// the least greater element on its right
import java.io.*;
class BinarySearchTree{
// A binary Tree node
class Node
{
int data;
Node left, right;
Node(int d)
{
data = d;
left = right = null;
}
}
// Root of BST
static Node root;
static Node succ;
// Constructor
BinarySearchTree()
{
root = null;
succ = null;
}
// A utility function to insert a new node with
// given data in BST and find its successor
Node insert(Node node, int data)
{
// If the tree is empty, return a new node
if (node == null)
{
node = new Node(data);
}
// If key is smaller than root's key,
// go to left subtree and set successor
// as current node
if (data < node.data)
{
succ = node;
node.left = insert(node.left, data);
}
// Go to right subtree
else if (data > node.data)
node.right = insert(node.right, data);
return node;
}
// Function to replace every element with the
// least greater element on its right
static void replace(int arr[], int n)
{
BinarySearchTree tree = new BinarySearchTree();
// start from right to left
for(int i = n - 1; i >= 0; i--)
{
succ = null;
// Insert current element into BST and
// find its inorder successor
root = tree.insert(root, arr[i]);
// Replace element by its inorder
// successor in BST
if (succ != null)
arr[i] = succ.data;
// No inorder successor
else
arr[i] = -1;
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = new int[] { 8, 58, 71, 18, 31,
32, 63, 92, 43, 3,
91, 93, 25, 80, 28 };
int n = arr.length;
replace(arr, n);
for(int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
// The code is contributed by Tushar Bansal
Python3
# Python3 program to replace every element
# with the least greater element on its right
# A binary Tree node
class Node:
def __init__(self, d):
self.data = d
self.left = None
self.right = None
# A utility function to insert a new node with
# given data in BST and find its successor
def insert(node, data):
global succ
# If the tree is empty, return a new node
root = node
if (node == None):
return Node(data)
# If key is smaller than root's key, go to left
# subtree and set successor as current node
if (data < node.data):
#print("1")
succ = node
root.left = insert(node.left, data)
# Go to right subtree
elif (data > node.data):
root.right = insert(node.right, data)
return root
# Function to replace every element with the
# least greater element on its right
def replace(arr, n):
global succ
root = None
# Start from right to left
for i in range(n - 1, -1, -1):
succ = None
# Insert current element into BST and
# find its inorder successor
root = insert(root, arr[i])
# Replace element by its inorder
# successor in BST
if (succ):
arr[i] = succ.data
# No inorder successor
else:
arr[i] = -1
return arr
# Driver code
if __name__ == '__main__':
arr = [ 8, 58, 71, 18, 31, 32, 63,
92, 43, 3, 91, 93, 25, 80, 28 ]
n = len(arr)
succ = None
arr = replace(arr, n)
print(*arr)
# This code is contributed by mohit kumar 29
C#
// C# program to replace every element with
// the least greater element on its right
using System;
class BinarySearchTree{
// A binary Tree node
public class Node
{
public int data;
public Node left, right;
public Node(int d)
{
data = d;
left = right = null;
}
}
// Root of BST
public static Node root;
public static Node succ;
// Constructor
public BinarySearchTree()
{
root = null;
succ = null;
}
// A utility function to insert a new node with
// given data in BST and find its successor
public static Node insert(Node node, int data)
{
// If the tree is empty, return a new node
if (node == null)
{
node = new Node(data);
}
// If key is smaller than root's key,
// go to left subtree and set successor
// as current node
if (data < node.data)
{
succ = node;
node.left = insert(node.left, data);
}
// Go to right subtree
else if (data > node.data)
{
node.right = insert(node.right, data);
}
return node;
}
// Function to replace every element with the
// least greater element on its right
public static void replace(int[] arr, int n)
{
//BinarySearchTree tree = new BinarySearchTree();
// Start from right to left
for(int i = n - 1; i >= 0; i--)
{
succ = null;
// Insert current element into BST and
// find its inorder successor
root = BinarySearchTree.insert(root, arr[i]);
// Replace element by its inorder
// successor in BST
if (succ != null)
{
arr[i] = succ.data;
}
// No inorder successor
else
{
arr[i] = -1;
}
}
}
// Driver code
static public void Main()
{
int[] arr = { 8, 58, 71, 18, 31,
32, 63, 92, 43, 3,
91, 93, 25, 80, 28 };
int n = arr.Length;
replace(arr, n);
for(int i = 0; i < n; i++)
{
Console.Write(arr[i]+" ");
}
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript program to
// replace every element with
// the least greater element
// on its right
// A binary Tree node
class Node{
constructor(d)
{
this.data=d;
this.left=this.right=null;
}
}
// Root of BST
let root=null;
let succ=null;
// A utility function to insert a new node with
// given data in BST and find its successor
function insert(node,data)
{
// If the tree is empty, return a new node
if (node == null)
{
node = new Node(data);
}
// If key is smaller than root's key,
// go to left subtree and set successor
// as current node
if (data < node.data)
{
succ = node;
node.left = insert(node.left, data);
}
// Go to right subtree
else if (data > node.data)
node.right = insert(node.right, data);
return node;
}
// Function to replace every element with the
// least greater element on its right
function replace(arr,n)
{
// start from right to left
for(let i = n - 1; i >= 0; i--)
{
succ = null;
// Insert current element into BST and
// find its inorder successor
root = insert(root, arr[i]);
// Replace element by its inorder
// successor in BST
if (succ != null)
arr[i] = succ.data;
// No inorder successor
else
arr[i] = -1;
}
}
// Driver code
let arr=[8, 58, 71, 18, 31,
32, 63, 92, 43, 3,
91, 93, 25, 80, 28 ];
let n = arr.length;
replace(arr, n);
for(let i = 0; i < n; i++)
document.write(arr[i] + " ");
// This code is contributed by unknown2108
</script>
Producción
18 63 80 25 32 43 80 93 80 25 93 -1 28 -1 -1
La complejidad temporal en el peor de los casos de la solución anterior también es O(n 2 ) ya que utiliza BST. El peor de los casos ocurrirá cuando la array se ordene en orden ascendente o descendente. La complejidad se puede reducir fácilmente a O (nlogn) mediante el uso de árboles equilibrados como árboles rojo-negro.
Otro enfoque:
Podemos usar el siguiente elemento mayor usando el algoritmo de pila para resolver este problema en el tiempo O (Nlog (N)) y el espacio O (N) .
Algoritmo:
- Primero, tomamos una array de pares, a saber, temp, y almacenamos cada elemento y su índice en esta array, es decir, temp[i] almacenará {arr[i],i} .
- Ordene la array según los elementos de la array.
- Ahora obtenga el siguiente índice mayor para todos y cada uno de los índices de la array temporal en una array, a saber, el índice mediante el uso del elemento siguiente mayor mediante la pila.
- Ahora index[i] almacena el índice del siguiente elemento menor mayor del elemento temp[i].first y si index[i] es -1, entonces significa que no hay ningún elemento menor mayor del elemento temp[i] .segundo en su lado derecho.
- Ahora tome una array de resultados donde el resultado [i] será igual a [índices [temp [i]. segundo]] si el índice [i] no es -1; de lo contrario, el resultado [i] será igual a -1.
A continuación se muestra la implementación del enfoque anterior.
C++
#include <bits/stdc++.h>
using namespace std;
// function to get the next least greater index for each and
// every temp.second of the temp array using stack this
// function is similar to the Next Greater element for each
// and every element of an array using stack difference is
// we are finding the next greater index not value and the
// indexes are stored in the temp[i].second for all i
vector<int> nextGreaterIndex(vector<pair<int, int> >& temp)
{
int n = temp.size();
// initially result[i] for all i is -1
vector<int> res(n, -1);
stack<int> stack;
for (int i = 0; i < n; i++) {
// if the stack is empty or this index is smaller
// than the index stored at top of the stack then we
// push this index to the stack
if (stack.empty() || temp[i].second < stack.top())
stack.push(
temp[i].second); // notice temp[i].second is
// the index
// else this index (i.e. temp[i].second) is greater
// than the index stored at top of the stack we pop
// all the indexes stored at stack's top and for all
// these indexes we make this index i.e.
// temp[i].second as their next greater index
else {
while (!stack.empty()
&& temp[i].second > stack.top()) {
res[stack.top()] = temp[i].second;
stack.pop();
}
// after that push the current index to the stack
stack.push(temp[i].second);
}
}
// now res will store the next least greater indexes for
// each and every indexes stored at temp[i].second for
// all i
return res;
}
// now we will be using above function for finding the next
// greater index for each and every indexes stored at
// temp[i].second
vector<int> replaceByLeastGreaterUsingStack(int arr[],
int n)
{
// first of all in temp we store the pairs of {arr[i].i}
vector<pair<int, int> > temp;
for (int i = 0; i < n; i++) {
temp.push_back({ arr[i], i });
}
// we sort the temp according to the first of the pair
// i.e value
sort(temp.begin(),temp.end(),[](const pair<int,int> &a,const pair<int,int> &b){
if(a.first==b.first)
return a.second>b.second;
return a.first<b.first;});
// now indexes vector will store the next greater index
// for each temp[i].second index
vector<int> indexes = nextGreaterIndex(temp);
// we initialize a result vector with all -1
vector<int> res(n, -1);
for (int i = 0; i < n; i++) {
// now if there is no next greater index after the
// index temp[i].second the result will be -1
// otherwise the result will be the element of the
// array arr at index indexes[temp[i].second]
if (indexes[temp[i].second] != -1)
res[temp[i].second]
= arr[indexes[temp[i].second]];
}
// return the res which will store the least greater
// element of each and every element in the array at its
// right side
return res;
}
// driver code
int main()
{
int arr[] = { 8, 58, 71, 18, 31, 32, 63, 92,
43, 3, 91, 93, 25, 80, 28 };
int n = sizeof(arr) / sizeof(int);
auto res = replaceByLeastGreaterUsingStack(arr, n);
cout << "Least Greater elements on the right side are "
<< endl;
for (int i : res)
cout << i << ' ';
cout << endl;
return 0;
} // this code is contributed by Dipti Prakash Sinha
Java
// Java program for above approach
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;
public class GFF {
// function to get the next least greater index for each
// and every temp.second of the temp array using stack
// this function is similar to the Next Greater element
// for each and every element of an array using stack
// difference is we are finding the next greater index
// not value and the indexes are stored in the
// temp[i].second for all i
static int[] nextGreaterIndex(ArrayList<int[]> temp)
{
int n = temp.size();
// initially result[i] for all i is -1
int[] res = new int[n];
Arrays.fill(res, -1);
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < n; i++) {
// if the stack is empty or this index is
// smaller than the index stored at top of the
// stack then we push this index to the stack
if (stack.empty()
|| temp.get(i)[1] < stack.peek())
stack.push(temp.get(
i)[1]); // notice temp[i].second is
// the index
// else this index (i.e. temp[i].second) is
// greater than the index stored at top of the
// stack we pop all the indexes stored at
// stack's top and for all these indexes we make
// this index i.e. temp[i].second as their next
// greater index
else {
while (!stack.empty()
&& temp.get(i)[1] > stack.peek()) {
res[stack.peek()] = temp.get(i)[1];
stack.pop();
}
// after that push the current index to the
// stack
stack.push(temp.get(i)[1]);
}
}
// now res will store the next least greater indexes
// for each and every indexes stored at
// temp[i].second for all i
return res;
}
// now we will be using above function for finding the
// next greater index for each and every indexes stored
// at temp[i].second
static int[] replaceByLeastGreaterUsingStack(int arr[],
int n)
{
// first of all in temp we store the pairs of
// {arr[i].i}
ArrayList<int[]> temp = new ArrayList<int[]>();
for (int i = 0; i < n; i++) {
temp.add(new int[] { arr[i], i });
}
// we sort the temp according to the first of the
// pair i.e value
Collections.sort(temp, (a, b) -> {
if (a[0] == b[0])
return a[1] - b[1];
return a[0] - b[0];
});
// now indexes vector will store the next greater
// index for each temp[i].second index
int[] indexes = nextGreaterIndex(temp);
// we initialize a result vector with all -1
int[] res = new int[n];
Arrays.fill(res, -1);
for (int i = 0; i < n; i++) {
// now if there is no next greater index after
// the index temp[i].second the result will be
// -1 otherwise the result will be the element
// of the array arr at index
// indexes[temp[i].second]
if (indexes[temp.get(i)[1]] != -1)
res[temp.get(i)[1]]
= arr[indexes[temp.get(i)[1]]];
}
// return the res which will store the least greater
// element of each and every element in the array at
// its right side
return res;
}
// driver code
public static void main(String[] args)
{
int arr[] = { 8, 58, 71, 18, 31, 32, 63, 92,
43, 3, 91, 93, 25, 80, 28 };
int n = arr.length;
int[] res = replaceByLeastGreaterUsingStack(arr, n);
System.out.println(
"Least Greater elements on the right side are ");
for (int i : res)
System.out.print(i + " ");
System.out.println();
}
}
// This code is contributed by Lovely Jain
Python3
# function to get the next least greater index for each and
# every temp[1] of the temp array using stack this
# function is similar to the Next Greater element for each
# and every element of an array using stack difference is
# we are finding the next greater index not value and the
# indexes are stored in the temp[i][1] for all i
def nextGreaterIndex(temp):
n = len(temp)
# initially result[i] for all i is -1
res = [-1 for i in range(n)]
stack = []
for i in range(n):
# if the stack is empty or this index is smaller
# than the index stored at top of the stack then we
# append this index to the stack
if (len(stack)==0 or temp[i][1] < stack[-1]):
stack.append(temp[i][1]); # notice temp[i][1] is
# the index
# else this index (i.e. temp[i][1]) is greater
# than the index stored at top of the stack we pop
# all the indexes stored at stack's top and for all
# these indexes we make this index i.e.
# temp[i][1] as their next greater index
else:
while (len(stack)>0 and temp[i][1] > stack[-1]):
res[stack[-1]] = temp[i][1]
stack.pop()
# after that append the current index to the stack
stack.append(temp[i][1])
# now res will store the next least greater indexes for
# each and every indexes stored at temp[i][1] for
# all i
return res
# now we will be using above function for finding the next
# greater index for each and every indexes stored at
# temp[i][1]
def replaceByLeastGreaterUsingStack(arr, n):
# first of all in temp we store the pairs of {arr[i].i}
temp = []
for i in range(n):
temp.append([ arr[i], i ])
# we sort the temp according to the first of the pair
# i.e value
temp.sort()
# now indexes vector will store the next greater index
# for each temp[i][1] index
indexes = nextGreaterIndex(temp)
# we initialize a result vector with all -1
res = [-1 for i in range(n)]
for i in range(n):
# now if there is no next greater index after the
# index temp[i][1] the result will be -1
# otherwise the result will be the element of the
# array arr at index indexes[temp[i][1]]
if (indexes[temp[i][1]] != -1):
res[temp[i][1]] = arr[indexes[temp[i][1]]]
# return the res which will store the least greater
# element of each and every element in the array at its
# right side
return res
# driver code
arr = [ 8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28 ]
n = len(arr)
res = replaceByLeastGreaterUsingStack(arr, n)
print("Least Greater elements on the right side are ")
for i in res:
print(i,end = ' ')
print()
# this code is contributed by shinjanpatra
Javascript
<script>
// function to get the next least greater index for each and
// every temp[1] of the temp array using stack this
// function is similar to the Next Greater element for each
// and every element of an array using stack difference is
// we are finding the next greater index not value and the
// indexes are stored in the temp[i][1] for all i
function mycmp(a,b){
if(a[0] == b[0])
return b[1] - a[1];
return a[0] - b[0];
}
function nextGreaterIndex(temp)
{
let n = temp.length;
// initially result[i] for all i is -1
let res = new Array(n).fill(-1);
let stack = [];
for (let i = 0; i < n; i++) {
// if the stack is empty or this index is smaller
// than the index stored at top of the stack then we
// push this index to the stack
if (stack.length == 0 || temp[i][1] < stack[stack.length-1])
stack.push(temp[i][1]); // notice temp[i][1] is
// the index
// else this index (i.e. temp[i][1]) is greater
// than the index stored at top of the stack we pop
// all the indexes stored at stack's top and for all
// these indexes we make this index i.e.
// temp[i][1] as their next greater index
else {
while (stack.length > 0 && temp[i][1] > stack[stack.length-1]) {
res[stack[stack.length-1]] = temp[i][1];
stack.pop();
}
// after that push the current index to the stack
stack.push(temp[i][1]);
}
}
// now res will store the next least greater indexes for
// each and every indexes stored at temp[i][1] for
// all i
return res;
}
// now we will be using above function for finding the next
// greater index for each and every indexes stored at
// temp[i][1]
function replaceByLeastGreaterUsingStack(arr,n)
{
// first of all in temp we store the pairs of {arr[i].i}
let temp = [];
for (let i = 0; i < n; i++) {
temp.push([arr[i], i]);
}
// we sort the temp according to the first of the pair
// i.e value
temp.sort(mycmp);
// now indexes vector will store the next greater index
// for each temp[i][1] index
let indexes = nextGreaterIndex(temp);
// we initialize a result vector with all -1
let res = new Array(n).fill(-1);
for (let i = 0; i < n; i++) {
// now if there is no next greater index after the
// index temp[i][1] the result will be -1
// otherwise the result will be the element of the
// array arr at index indexes[temp[i][1]]
if (indexes[temp[i][1]] != -1)
res[temp[i][1]]
= arr[indexes[temp[i][1]]];
}
// return the res which will store the least greater
// element of each and every element in the array at its
// right side
return res;
}
// driver code
let arr = [ 8, 58, 71, 18, 31, 32, 63, 92,
43, 3, 91, 93, 25, 80, 28 ];
let n = arr.length;
let res = replaceByLeastGreaterUsingStack(arr, n);
document.write("Least Greater elements on the right side are ","</br>");
for (let i of res)
document.write(i,' ');
document.write("</br>");
// this code is contributed by shinjanpatra
</script>
Producción
Least Greater elements on the right side are 18 63 80 25 32 43 80 93 80 25 93 -1 28 -1 -1
Otro enfoque con set
Una forma diferente de pensar en el problema es hacer una lista de nuestros requisitos y luego pensar en ello para encontrar una solución. Si recorremos la array desde atrás, necesitamos una estructura de datos (ds) para admitir:
- Inserte un elemento en nuestro ds en orden ordenado (para que en cualquier momento los elementos en nuestro ds estén ordenados)
- Encontrar el límite superior del elemento actual (el límite superior dará un elemento mayor de nuestro ds si está presente)
Observando atentamente nuestros requerimientos, un conjunto es lo que viene a la mente.
¿Por qué no multiset? Bueno, podemos usar un conjunto múltiple, pero no es necesario almacenar un elemento más de una vez.
Codifiquemos nuestro enfoque
Complejidad de tiempo y espacio : insertamos cada elemento en nuestro conjunto y encontramos el límite superior para cada elemento usando un bucle, por lo que su complejidad de tiempo es O (n * log (n)). Estamos almacenando cada elemento en nuestro conjunto, por lo que la complejidad del espacio es O (n)
C++
#include <iostream>
#include <vector>
#include <set>
using namespace std;
void solve(vector<int>& arr) {
set<int> s;
vector<int> ans(arr.size());
for(int i=arr.size()-1;i>=0;i--) { //traversing the array backwards
s.insert(arr[i]); // inserting the element into set
auto it = s.upper_bound(arr[i]); // finding upper bound
if(it == s.end()) arr[i] = -1; // if upper_bound does not exist then -1
else arr[i] = *it; // if upper_bound exists, lets take it
}
}
void printArray(vector<int>& arr) {
for(int i : arr) cout << i << " ";
cout << "\n";
}
int main() {
vector<int> arr = {8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28};
printArray(arr);
solve(arr);
printArray(arr);
return 0;
}
Producción
8 58 71 18 31 32 63 92 43 3 91 93 25 80 28 18 63 80 25 32 43 80 93 80 25 93 -1 28 -1 -1
Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA