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>
-1 10 -1 10 -1 20
Complejidad de tiempo: O(n Log n)
Espacio Auxiliar: O(n)