Dada una array arr[] que consta de N enteros distintos, la tarea es imprimir para cada elemento de la array, todos los elementos mayores presentes a su izquierda.
Ejemplos:
Entrada: arr[] = {5, 3, 9, 0, 16, 12}
Salida:
5:
3: 5
9:
0: 9 5 3
16:
12: 16Entrada: arr[] = {1, 2, 0}
Salida:
1:
2:
0: 2 1
Enfoque ingenuo: el enfoque más simple para resolver el problema es recorrer la array y, para cada elemento de la array, recorrer todos sus elementos anteriores e imprimir los que son mayores que el elemento actual.
C++
// C++ program for Naive approach
#include <bits/stdc++.h>
using namespace std;
// Function to print all greater elements on the left of each array element
void printGreater(vector<int>& arr)
{
// store the size of array in variable n
int n = arr.size();
for (int i = 0; i < n; i++)
{
// result is used to store elements which are greater than current element present left side of current element
vector<int> result;
// traversing all the elements which are left of current element arr[i]
for (int j = i - 1; j >= 0; j--)
{
//checking whether arr[j] (left element) is greater than current element or not
// if yes then insert the element to the result vector
if (arr[j] > arr[i])
{
result.push_back(arr[j]);
}
}
cout << arr[i] << ": ";
//printing all the elements present in result vector
for (int k = 0; k < result.size(); k++)
{
cout << result[k] << " ";
}
cout << endl;
}
}
//Driver Code
int main()
{
vector<int> arr{5, 3, 9, 0, 16, 12};
printGreater(arr);
return 0;
}
Java
// java program for Naive approach
import java.util.*;
class GFG{
// Function to print all greater elements on the left of each array element
static void printGreater(ArrayList<Integer> arr)
{
// store the size of array in variable n
int n = arr.size();
for (int i = 0; i < n; i++)
{
// result is used to store elements which
// are greater than current element present
// left side of current element
ArrayList<Integer> result
= new ArrayList<Integer>();
// traversing all the elements which
// are left of current element arr[i]
for (int j = i - 1; j >= 0; j--)
{
// checking whether arr[j] (left element) is
// greater than current element or not
// if yes then insert the element to the result vector
if (arr.get(j) > arr.get(i))
{
result.add(arr.get(j));
}
}
System.out.print(arr.get(i) + ": ");
// printing all the elements present in result vector
for (int k = 0; k < result.size(); k++)
{
System.out.print(result.get(k) +" ");
}
System.out.println();
}
}
// Driver Code
public static void main(String args[])
{
ArrayList<Integer> arr = new ArrayList<Integer>(Arrays.asList(5, 3, 9, 0, 16, 12));
printGreater(arr);
}
}
// This code is contributed by bgangwar59.
Python3
# Python3 program for Naive approach
# Function to print all greater
# elements on the left of each
# array element
def printGreater(arr):
# Store the size of array
# in variable n
n = len(arr)
for i in range(n):
# Result is used to store elements
# which are greater than current
# element present left side of
# current element
result = []
# Traversing all the elements
# which are left of current
# element arr[i]
j = i - 1
while(j >= 0):
# Checking whether arr[j] (left element)
# is greater than current element or not
# if yes then insert the element to the
# result vector
if (arr[j] > arr[i]):
result.append(arr[j])
j -= 1
print(arr[i], end = ": ")
# Printing all the elements present
# in result vector
for k in range(len(result)):
print(result[k], end = " ")
print("\n", end = "")
# Driver Code
if __name__ == '__main__':
arr = [ 5, 3, 9, 0, 16, 12 ]
printGreater(arr)
# This code is contributed by ipg2016107
C#
// C# program for Naive approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to print all greater elements on the left of
// each array element
static void printGreater(int[] arr)
{
// store the size of array in variable n
int n = arr.Length;
for (int i = 0; i < n; i++)
{
// result is used to store elements which are
// greater than current element present left
// side of current element
List<int> result = new List<int>();
// traversing all the elements which are left of
// current element arr[i]
for (int j = i - 1; j >= 0; j--)
{
// checking whether arr[j] (left element) is
// greater than current element or not
// if yes then insert the element to the
// result vector
if (arr[j] > arr[i]) {
result.Add(arr[j]);
}
}
Console.Write(arr[i] + ": ");
// printing all the elements present in result
// vector
for (int k = 0; k < result.Count; k++) {
Console.Write(result[k] + " ");
}
Console.WriteLine();
}
}
// Driver Code
public static void Main()
{
int[] arr = { 5, 3, 9, 0, 16, 12 };
printGreater(arr);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program for Naive approach
// Function to print all greater elements on the left of
// each array element
function printGreater(arr)
{
// store the size of array in variable n
let n = arr.length;
for (let i = 0; i < n; i++)
{
// result is used to store elements which are
// greater than current element present left
// side of current element
let result = [];
// traversing all the elements which are left of
// current element arr[i]
for (let j = i - 1; j >= 0; j--)
{
// checking whether arr[j] (left element) is
// greater than current element or not
// if yes then insert the element to the
// result vector
if (arr[j] > arr[i]) {
result.push(arr[j]);
}
}
document.write(arr[i] + ": ");
// printing all the elements present in result
// vector
for (let k = 0; k < result.length; k++) {
document.write(result[k] + " ");
}
document.write("</br>");
}
}
let arr = [ 5, 3, 9, 0, 16, 12 ];
printGreater(arr);
// This code is contributed by mukesh07.
</script>
Producción
5: 3: 5 9: 0: 9 3 5 16: 12: 16
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es hacer uso de árboles de búsqueda binarios autoequilibrados . Establecer en C++ se implementa mediante BST de autoequilibrio y se puede utilizar para resolver este problema. Siga los pasos para resolver el problema:
- Inicializa un Set s , que almacena los elementos en orden no decreciente.
- Recorra la array sobre los índices 0 a N – 1 y realice las siguientes operaciones:
- Inserte arr[i] en el conjunto s .
- Iterar desde el comienzo del Conjunto hasta p e imprimir los elementos en el Conjunto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print all greater elements
// on the left of each array element
void printGreater(vector<int>& arr)
{
int n = arr.size();
// Set to implement
// self-balancing BSTs
set<int, greater<int> > s;
// Traverse the array
for (int i = 0; i < n; i++) {
// Insert the current
// element into the set
auto p = s.insert(arr[i]);
auto j = s.begin();
cout << arr[i] << ": ";
// Iterate through the set
while (j != p.first) {
// Print the element
cout << *j << " ";
j++;
}
cout << endl;
}
}
// Driver Code
int main()
{
vector<int> arr{ 5, 3, 9, 0, 16, 12 };
printGreater(arr);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to print all greater elements
// on the left of each array element
static void printGreater(int arr[])
{
int n = arr.length;
// Set to implement
// self-balancing BSTs
TreeSet<Integer> s = new TreeSet<>(
Collections.reverseOrder());
// Traverse the array
for(int i = 0; i < n; i++)
{
// Insert the current
// element into the set
s.add(arr[i]);
System.out.print(arr[i] + ": ");
// Iterate through the set
for(int v : s)
{
if (v == arr[i])
break;
// Print the element
System.out.print(v + " ");
}
System.out.println();
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 5, 3, 9, 0, 16, 12 };
printGreater(arr);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach # Function to print all greater elements # on the left of each array element def printGreater(arr): n = len(arr) # Set to implement # self-balancing BSTs s = set([]) # Traverse the array for i in range(n): # Insert the current # element into the set s.add(arr[i]) print(arr[i], ": ", sep = "", end = "") temp = list(s) temp.sort() temp.reverse() # Iterate through the set for v in range(len(temp)): if (temp[v] == arr[i]): break # Print the element print(temp[v], end = " ") print() arr = [5, 3, 9, 0, 16, 12] printGreater(arr) # This code is contributed by divyesh072019.
C#
// C# Program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to print all greater elements
// on the left of each array element
static void printGreater(int[] arr)
{
int n = arr.Length;
// Set to implement
// self-balancing BSTs
HashSet<int> s = new HashSet<int>();
// Traverse the array
for(int i = 0; i < n; i++)
{
// Insert the current
// element into the set
s.Add(arr[i]);
Console.Write(arr[i] + ": ");
List<int> temp = new List<int>();
// Iterate through the set
foreach(int v in s)
{
temp.Add(v);
}
temp.Sort();
temp.Reverse();
// Iterate through the set
for(int v = 0; v < temp.Count; v++)
{
if (temp[v] == arr[i])
{
break;
}
// Print the element
Console.Write(temp[v] + " ");
}
Console.WriteLine();
}
}
// Driver code
static void Main() {
int[] arr = { 5, 3, 9, 0, 16, 12 };
printGreater(arr);
}
}
// This code is contributed by rameshtravel07.
Javascript
<script>
// JavaScript program for the above approach
// Function to print all greater elements
// on the left of each array element
function printGreater(arr)
{
let n = arr.length;
// Set to implement
// self-balancing BSTs
let s = new Set();
// Traverse the array
for(let i = 0; i < n; i++)
{
// Insert the current
// element into the set
s.add(arr[i]);
document.write(arr[i] + ": ");
let temp=Array.from(s).sort(function(a,b){return b-a;});
// Iterate through the set
for(let v=0;v< temp.length;v++)
{
if (temp[v] == arr[i])
break;
// Print the element
document.write(temp[v] + " ");
}
document.write("<br>");
}
}
// Driver Code
let arr=[5, 3, 9, 0, 16, 12];
printGreater(arr);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
5: 3: 5 9: 0: 9 5 3 16: 12: 16
Complejidad del Tiempo : O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA