Dada una array de enteros, encuentre el más cercano (sin considerar la distancia, sino el valor) mayor o el mismo valor a la izquierda de cada elemento. Si un elemento no tiene un valor mayor o igual en el lado izquierdo, imprima -1.
Ejemplos:
Entrada: arr[] = {10, 5, 11, 6, 20, 12}
Salida: -1, 10, -1, 10, -1, 20
El primer elemento no tiene nada en el lado izquierdo, por lo que la respuesta para el primero es -1.
Segundo, el elemento 5 tiene 10 a la izquierda, por lo que la respuesta es 10.
El tercer elemento 11 no tiene nada mayor ni igual, por lo que la respuesta es -1.
El cuarto elemento 6 tiene 10 como valor de cierre sabio, por lo que la respuesta es 10
De manera similar, obtenemos valores para los elementos quinto y sexto.
Una solución simple es ejecutar dos bucles anidados. Elegimos un elemento externo uno por uno. Para cada elemento elegido, nos desplazamos hacia la izquierda y encontramos el elemento mayor más cercano (en términos de valor). La complejidad temporal de esta solución es O(n*n)
C++
#include <bits/stdc++.h>
using namespace std;
// function for ceiling in left side for every element in an
// array
void printPrevGreater(int arr[], int n)
{
cout << "-1"
<< " "; // for first element
for (int i = 1; i < n; i++) {
int diff = INT_MAX;
for (int j = 0; j < i;
j++) // traverse left side to i-th element
{
if (arr[j] >= arr[i])
diff = min(diff, arr[j] - arr[i]);
}
if (diff == INT_MAX)
cout << "-1"
<< " "; // if not found at left side
else
cout << arr[i] + diff << " ";
}
}
// Driver code
int main()
{
int arr[] = { 10, 5, 11, 10, 20, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
printPrevGreater(arr, n);
return 0;
}
// This code is contributed by
// @itsrahulhere_
Java
import java.util.*;
class GFG {
// function for ceiling in left side for every element in an
// array
static void printPrevGreater(int arr[], int n) {
System.out.print("-1" + " "); // for first element
for (int i = 1; i < n; i++) {
int diff = Integer.MAX_VALUE;
for (int j = 0; j < i; j++) // traverse left side to i-th element
{
if (arr[j] >= arr[i])
diff = Math.min(diff, arr[j] - arr[i]);
}
if (diff == Integer.MAX_VALUE)
System.out.print("-1" + " "); // if not found at left side
else
System.out.print(arr[i] + diff + " ");
}
}
// Driver code
public static void main(String[] args) {
int arr[] = { 10, 5, 11, 10, 20, 12 };
int n = arr.length;
printPrevGreater(arr, n);
}
}
// This code is contributed by Rajput-Ji
Python3
import sys
# function for ceiling in left side for every element in an
# array
def printPrevGreater(arr,n):
print("-1",end = ' ') # for first element
for i in range(1,n):
diff = sys.maxsize
for j in range(i): # traverse left side to i-th element
if (arr[j] >= arr[i]):
diff = min(diff, arr[j] - arr[i])
if diff == sys.maxsize :
print("-1",end = " ") # if not found at left side
else :
print(arr[i] + diff ,end = ' ')
# Driver code
arr = [ 10, 5, 11, 10, 20, 12 ]
n = len(arr)
printPrevGreater(arr, n)
# This code is contributed by shinjanpatra
C#
using System;
public class GFG {
// function for ceiling in left side for every element in an
// array
static void printPrevGreater(int []arr, int n) {
Console.Write("-1" + " "); // for first element
for (int i = 1; i < n; i++) {
int diff = int.MaxValue;
for (int j = 0; j < i; j++) // traverse left side to i-th element
{
if (arr[j] >= arr[i])
diff = Math.Min(diff, arr[j] - arr[i]);
}
if (diff == int.MaxValue)
Console.Write("-1" + " "); // if not found at left side
else
Console.Write(arr[i] + diff + " ");
}
}
// Driver code
public static void Main(String[] args) {
int []arr = { 10, 5, 11, 10, 20, 12 };
int n = arr.Length;
printPrevGreater(arr, n);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// function for ceiling in left side for every element in an
// array
function printPrevGreater(arr , n) {
document.write("-1" + " "); // for first element
for (i = 1; i < n; i++) {
var diff = Number.MAX_VALUE;
for (j = 0; j < i; j++) // traverse left side to i-th element
{
if (arr[j] >= arr[i])
diff = Math.min(diff, arr[j] - arr[i]);
}
if (diff == Number.MAX_VALUE)
document.write("-1" + " "); // if not found at left side
else
document.write(arr[i] + diff + " ");
}
}
// Driver code
var arr = [ 10, 5, 11, 10, 20, 12 ];
var n = arr.length;
printPrevGreater(arr, n);
// This code is contributed by Rajput-Ji
</script>
Producción:
-1 10 -1 10 -1 20
Complejidad temporal: O(n * n)
Espacio auxiliar: O(1)
Una solución eficiente es usar Self-Balancing BST (Implementado como se establece en C++ y TreeSet en Java). En un BST de autoequilibrio, podemos realizar operaciones tanto de inserción como más cercanas en tiempo O (Log n).
Usamos lower_bound() en C++ para encontrar el elemento mayor más cercano. Esta función funciona en el tiempo de inicio de sesión para un conjunto.
C++
// C++ implementation of efficient algorithm to find
// greater or same element on left side
#include <iostream>
#include <set>
using namespace std;
// Prints greater elements on left side of every element
void printPrevGreater(int arr[], int n)
{
set<int> s;
for (int i = 0; i < n; i++) {
// First search in set
auto it = s.lower_bound(arr[i]);
if (it == s.end()) // If no greater found
cout << "-1"
<< " ";
else
cout << *it << " ";
// Then insert
s.insert(arr[i]);
}
}
/* Driver program to test insertion sort */
int main()
{
int arr[] = { 10, 5, 11, 10, 20, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
printPrevGreater(arr, n);
return 0;
}
Java
// Java implementation of efficient algorithm
// to find greater or same element on left side
import java.util.TreeSet;
class GFG {
// Prints greater elements on left side
// of every element
static void printPrevGreater(int[] arr, int n)
{
TreeSet<Integer> ts = new TreeSet<>();
for (int i = 0; i < n; i++) {
Integer c = ts.ceiling(arr[i]);
if (c == null) // If no greater found
System.out.print(-1 + " ");
else
System.out.print(c + " ");
// Then insert
ts.add(arr[i]);
}
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 10, 5, 11, 10, 20, 12 };
int n = arr.length;
printPrevGreater(arr, n);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 implementation of efficient algorithm
# to find greater or same element on left side
# Prints greater elements
# on left side of every element
def printPrevGreater(arr, n):
s = set()
for i in range(0, n):
# First search in set
it = [x for x in s if x >= arr[i]]
if len(it) == 0: # If no greater found
print("-1", end = " ")
else:
print(min(it), end = " ")
# Then insert
s.add(arr[i])
# Driver Code
if __name__ == "__main__":
arr = [10, 5, 11, 10, 20, 12]
n = len(arr)
printPrevGreater(arr, n)
# This code is contributed by Rituraj Jain
C#
// C# implementation of efficient algorithm
// to find greater or same element on left side
using System;
using System.Collections.Generic;
class GFG {
// To get the minimum value
static int minimum(SortedSet<int> ss)
{
int min = int.MaxValue;
foreach(int i in ss) if (i < min)
min = i;
return min;
}
// Prints greater elements on left side
// of every element
static void printPrevGreater(int[] arr, int n)
{
SortedSet<int> s = new SortedSet<int>();
for (int i = 0; i < n; i++) {
SortedSet<int> ss = new SortedSet<int>();
// First search in set
foreach(int x in s) if (x >= arr[i])
ss.Add(x);
if (ss.Count == 0) // If no greater found
Console.Write(-1 + " ");
else
Console.Write(minimum(ss) + " ");
// Then insert
s.Add(arr[i]);
}
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 10, 5, 11, 10, 20, 12 };
int n = arr.Length;
printPrevGreater(arr, n);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of efficient algorithm to find
// greater or same element on left side
// To get the minimum value
function minimum(ss)
{
var min = 1000000000;
ss.forEach(i => {
if (i < min)
min = i;
});
return min;
}
// Prints greater elements on left side of every element
function printPrevGreater(arr, n)
{
var s = new Set();
for (var i = 0; i < n; i++) {
var ss = new Set();
// First search in set
s.forEach(x => {
if(x >= arr[i])
ss.add(x);
});
if (ss.size == 0) // If no greater found
document.write(-1 + " ");
else
document.write(minimum(ss) + " ");
// Then insert
s.add(arr[i]);
}
}
/* Driver program to test insertion sort */
var arr = [10, 5, 11, 10, 20, 12];
var n = arr.length;
printPrevGreater(arr, n);
</script>
Producción:
-1 10 -1 10 -1 20
Complejidad de tiempo: O(n Log n)
Espacio Auxiliar: O(n)