Dada una array arr[] de enteros distintos de tamaño N , la tarea es imprimir el recuento de elementos mayores en el lado izquierdo de cada elemento de la array.
Ejemplos:
Entrada: arr[] = {12, 1, 2, 3, 0, }
Salida: 0 1 1 1 4
Explicación:
Para el índice 0, no existe ningún elemento mayor en el lado izquierdo.
Para el índice 1, {12} es el elemento mayor en el lado izquierdo.
Para el índice 2, {12} es el elemento mayor en el lado izquierdo.
Para el índice 3, {12} es el elemento mayor en el lado izquierdo.
Para el índice 4, {12, 1, 2, 3} son elementos mayores en el lado izquierdo.
Por lo tanto, la salida es 0 1 1 1 4.Entrada: arr[] = {5, 4, 3, 2, 1}
Salida: 0 1 2 3 4
Enfoque ingenuo: el enfoque más simple para resolver el problema es recorrer la array y, para cada elemento de la array, recorrer hacia la izquierda y comparar cada elemento con el elemento actual. Finalmente, imprima el conteo de elementos mayores a su izquierda para cada elemento de la array.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente : el problema se puede resolver utilizando contenedores Set que se implementan mediante Self Balancing Binary Search Tree . Siga los pasos a continuación para resolver el problema.
- Cree un Conjunto vacío , St.
- Recorra la array e inserte cada elemento en St uno por uno.
- Encuentre el elemento mayor anterior de arr[i] usando la función upper_bound .
- Encuentra la distancia entre el elemento mayor anterior y el último elemento del conjunto usando la función de distancia .
- Almacene la distancia en la array, countLeftGreater[] .
- Imprime la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the count of greater
// elements on left of each array element
void display(int countLeftGreater[], int N)
{
for (int i = 0; i < N; i++) {
cout << countLeftGreater[i]
<< " ";
}
}
// Function to get the count of greater
// elements on left of each array element
void countGreater(int arr[], int N)
{
// Store distinct array
// elements in sorted order
set<int> St;
// Stores the count of greater
// elements on the left side
int countLeftGreater[N];
// Traverse the array
for (int i = 0; i < N; i++) {
// Insert array elements
// into the set
St.insert(arr[i]);
// Find previous greater element
auto it = St.upper_bound(arr[i]);
// Find the distance between the
// previous greater element of arr[i]
// and last element of the set
countLeftGreater[i]
= distance(it, St.end());
}
display(countLeftGreater, N);
}
// Driver Code
int main()
{
int arr[] = { 12, 1, 2, 3, 0, 11, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
countGreater(arr, N);
}
Java
// Java program to implement
// the above approach
import java.util.*;
import java.lang.*;
class GFG{
// Function to print the count of greater
// elements on left of each array element
static void display(int countLeftGreater[], int N)
{
for(int i = 0; i < N; i++)
{
System.out.print(countLeftGreater[i] + " ");
}
}
// Function to get the count of greater
// elements on left of each array element
static void countGreater(int arr[], int N)
{
// Store distinct array
// elements in sorted order
Set<Integer> St = new TreeSet<>();
// Stores the count of greater
// elements on the left side
int[] countLeftGreater = new int[N];
// Traverse the array
for(int i = 0; i < N; i++)
{
// Insert array elements
// into the set
St.add(arr[i]);
int it = 0;
// Find previous greater element
Iterator<Integer> iterator = St.iterator();
while (iterator.hasNext())
{
if (arr[i] < iterator.next())
{
break;
}
it++;
}
// Find the distance between the
// previous greater element of arr[i]
// and last element of the set
countLeftGreater[i] = Math.abs(it - St.size());
}
display(countLeftGreater, N);
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 12, 1, 2, 3, 0, 11, 4 };
int N = arr.length;
countGreater(arr, N);
}
}
// This code is contributed by offbeat
Python3
# Python3 program to implement # the above approach # Function to print the count of greater # elements on left of each array element def display(countLeftGreater, N): for i in range(N): print(countLeftGreater[i], end = " ") # Function to get the count of greater # elements on left of each array element def countGreater(arr, N): # Store distinct array # elements in sorted order St = set() # Stores the count of greater # elements on the left side countLeftGreater = [0] * (N) # Traverse the array for i in range(N): # Insert array elements # into the set St.add(arr[i]) it = 0 # Find previous greater element for st in St: if (arr[i] < st): break it += 1 # Find the distance between the # previous greater element of arr[i] # and last element of the set countLeftGreater[i] = abs(it - len(St)) display(countLeftGreater, N) # Driver code if __name__ == '__main__': arr = [ 12, 1, 2, 3, 0, 11, 4 ] N = len(arr) countGreater(arr, N) # This code is contributed by Rajput-Ji
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to print the count of greater
// elements on left of each array element
static void display(int []countLeftGreater, int N)
{
for(int i = 0; i < N; i++)
{
Console.Write(countLeftGreater[i] + " ");
}
}
// Function to get the count of greater
// elements on left of each array element
static void countGreater(int []arr, int N)
{
// Store distinct array
// elements in sorted order
List<int> St = new List<int>();
// Stores the count of greater
// elements on the left side
int[] countLeftGreater = new int[N];
// Traverse the array
for(int i = 0; i < N; i++)
{
// Insert array elements
// into the set
St.Add(arr[i]);
int it = 0;
St.Sort();
// Find previous greater element
foreach(int itr in St)
{
if (arr[i] < itr)
{
break;
}
it++;
}
// Find the distance between the
// previous greater element of arr[i]
// and last element of the set
countLeftGreater[i] = Math.Abs(it - St.Count);
}
display(countLeftGreater, N);
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 12, 1, 2, 3, 0, 11, 4 };
int N = arr.Length;
countGreater(arr, N);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Js program to implement
// the above approach
// Function to print the count of greater
// elements on left of each array element
function display( countLeftGreater, N)
{
for (let i = 0; i < N; i++) {
document.write(countLeftGreater[i] ," ");
}
}
// Function to get the count of greater
// elements on left of each array element
function countGreater(arr, N)
{
// Store distinct array
// elements in sorted order
let St = new Set();
// Stores the count of greater
// elements on the left side
let countLeftGreater = [];
// Traverse the array
for (let i = 0; i < N; i++) {
// Insert array elements
// into the set
St.add(arr[i]);
// Find previous greater element
let it = 0;
// Find previous greater element
//let a = Array.from(St);
//a.sort(function(a,b){return a-b});
for (let st of St){
if (arr[i] < st)
it += 1;
}
// Find the distance between the
// previous greater element of arr[i]
// and last element of the set
countLeftGreater[i]
= Math.abs(it);
}
display(countLeftGreater, N);
}
// Driver Code
let arr = [ 12, 1, 2, 3, 0, 11, 4 ];
let N = arr.length;
countGreater(arr, N);
</script>
0 1 1 1 4 1 2
Complejidad de tiempo: O(N 2 ) porque la función de distancia toma O(N) pero la implementación anterior es muy simple y funciona mejor que el algoritmo ingenuo en el caso promedio.
Espacio Auxiliar: O(N)
Nota: el enfoque anterior funciona para elementos únicos, pero para elementos duplicados simplemente reemplace Set con Multiset.
Publicación traducida automáticamente
Artículo escrito por manali21gupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA