Dada una array, para cada elemento, encuentre el valor del elemento más cercano a la derecha que tenga una frecuencia mayor que la del elemento actual. Si no existe una respuesta para una posición, entonces haga el valor ‘-1’.
Ejemplos:
Input : a[] = [1, 1, 2, 3, 4, 2, 1] Output : [-1, -1, 1, 2, 2, 1, -1] Explanation: Given array a[] = [1, 1, 2, 3, 4, 2, 1] Frequency of each element is: 3, 3, 2, 1, 1, 2, 3 Lets calls Next Greater Frequency element as NGF 1. For element a[0] = 1 which has a frequency = 3, As it has frequency of 3 and no other next element has frequency more than 3 so '-1' 2. For element a[1] = 1 it will be -1 same logic like a[0] 3. For element a[2] = 2 which has frequency = 2, NGF element is 1 at position = 6 with frequency of 3 > 2 4. For element a[3] = 3 which has frequency = 1, NGF element is 2 at position = 5 with frequency of 2 > 1 5. For element a[4] = 4 which has frequency = 1, NGF element is 2 at position = 5 with frequency of 2 > 1 6. For element a[5] = 2 which has frequency = 2, NGF element is 1 at position = 6 with frequency of 3 > 2 7. For element a[6] = 1 there is no element to its right, hence -1 Input : a[] = [1, 1, 1, 2, 2, 2, 2, 11, 3, 3] Output : [2, 2, 2, -1, -1, -1, -1, 3, -1, -1]
Enfoque ingenuo:
Una técnica simple de hash es usar valores a medida que se usa el índice para almacenar la frecuencia de cada elemento. Cree una lista suponga que almacena la frecuencia de cada número en la array. (Se requiere un solo recorrido). Ahora usa dos bucles.
El bucle exterior recoge todos los elementos uno por uno.
El bucle interno busca el primer elemento cuya frecuencia es mayor que la frecuencia del elemento actual.
Si se encuentra un elemento de mayor frecuencia, se imprime ese elemento; de lo contrario, se imprime -1.
Complejidad del tiempo: O(n*n)
Enfoque eficiente :
Podemos usar la estructura de datos hash y stack para resolver de manera eficiente muchos casos. Una técnica simple de hash es usar valores como índice y la frecuencia de cada elemento como valor. Usamos la estructura de datos de pila para almacenar la posición de los elementos en la array.
- Cree una lista para usar valores como índice para almacenar la frecuencia de cada elemento.
- Empuje la posición del primer elemento para apilar.
- Elija el resto de la posición de los elementos uno por uno y siga los siguientes pasos en bucle.
- Marque la posición del elemento actual como ‘i’.
- Si la frecuencia del elemento al que apunta la parte superior de la pila es mayor que la frecuencia del elemento actual, empuje la posición actual i a la pila
- Si la frecuencia del elemento al que apunta la parte superior de la pila es menor que la frecuencia del elemento actual y la pila no está vacía, siga estos pasos:
- continuar sacando la pila
- si la condición en el paso c falla, empuje la posición actual i a la pila
- Después de que termine el bucle en el paso 3, extraiga todos los elementos de la pila e imprima -1 ya que el siguiente elemento de mayor frecuencia no existe para ellos.
A continuación se muestra la implementación del problema anterior.
C++
// C++ program of Next Greater Frequency Element
#include <iostream>
#include <stack>
#include <stdio.h>
using namespace std;
/*NFG function to find the next greater frequency
element for each element in the array*/
void NFG(int a[], int n, int freq[])
{
// stack data structure to store the position
// of array element
stack<int> s;
s.push(0);
// res to store the value of next greater
// frequency element for each element
int res[n] = { 0 };
for (int i = 1; i < n; i++)
{
/* If the frequency of the element which is
pointed by the top of stack is greater
than frequency of the current element
then push the current position i in stack*/
if (freq[a[s.top()]] > freq[a[i]])
s.push(i);
else {
/*If the frequency of the element which
is pointed by the top of stack is less
than frequency of the current element, then
pop the stack and continuing popping until
the above condition is true while the stack
is not empty*/
while ( !s.empty()
&& freq[a[s.top()]] < freq[a[i]])
{
res[s.top()] = a[i];
s.pop();
}
// now push the current element
s.push(i);
}
}
while (!s.empty()) {
res[s.top()] = -1;
s.pop();
}
for (int i = 0; i < n; i++)
{
// Print the res list containing next
// greater frequency element
cout << res[i] << " ";
}
}
// Driver code
int main()
{
int a[] = { 1, 1, 2, 3, 4, 2, 1 };
int len = 7;
int max = INT16_MIN;
for (int i = 0; i < len; i++)
{
// Getting the max element of the array
if (a[i] > max) {
max = a[i];
}
}
int freq[max + 1] = { 0 };
// Calculating frequency of each element
for (int i = 0; i < len; i++)
{
freq[a[i]]++;
}
// Function call
NFG(a, len, freq);
return 0;
}
Java
// Java program of Next Greater Frequency Element
import java.util.*;
class GFG {
/*NFG function to find the next greater frequency
element for each element in the array*/
static void NFG(int a[], int n, int freq[])
{
// stack data structure to store the position
// of array element
Stack<Integer> s = new Stack<Integer>();
s.push(0);
// res to store the value of next greater
// frequency element for each element
int res[] = new int[n];
for (int i = 0; i < n; i++)
res[i] = 0;
for (int i = 1; i < n; i++)
{
/* If the frequency of the element which is
pointed by the top of stack is greater
than frequency of the current element
then push the current position i in stack*/
if (freq[a[s.peek()]] > freq[a[i]])
s.push(i);
else
{
/*If the frequency of the element which
is pointed by the top of stack is less
than frequency of the current element, then
pop the stack and continuing popping until
the above condition is true while the stack
is not empty*/
while (freq[a[s.peek()]] < freq[a[i]]
&& s.size() > 0)
{
res[s.peek()] = a[i];
s.pop();
}
// now push the current element
s.push(i);
}
}
while (s.size() > 0)
{
res[s.peek()] = -1;
s.pop();
}
for (int i = 0; i < n; i++)
{
// Print the res list containing next
// greater frequency element
System.out.print(res[i] + " ");
}
}
// Driver code
public static void main(String args[])
{
int a[] = { 1, 1, 2, 3, 4, 2, 1 };
int len = 7;
int max = Integer.MIN_VALUE;
for (int i = 0; i < len; i++)
{
// Getting the max element of the array
if (a[i] > max)
{
max = a[i];
}
}
int freq[] = new int[max + 1];
for (int i = 0; i < max + 1; i++)
freq[i] = 0;
// Calculating frequency of each element
for (int i = 0; i < len; i++)
{
freq[a[i]]++;
}
// Function call
NFG(a, len, freq);
}
}
// This code is contributed by Arnab Kundu
Python3
'''NFG function to find the next greater frequency
element for each element in the array'''
def NFG(a, n):
if (n <= 0):
print("List empty")
return []
# stack data structure to store the position
# of array element
stack = [0]*n
# freq is a dictionary which maintains the
# frequency of each element
freq = {}
for i in a:
freq[a[i]] = 0
for i in a:
freq[a[i]] += 1
# res to store the value of next greater
# frequency element for each element
res = [0]*n
# initialize top of stack to -1
top = -1
# push the first position of array in the stack
top += 1
stack[top] = 0
# now iterate for the rest of elements
for i in range(1, n):
''' If the frequency of the element which is
pointed by the top of stack is greater
than frequency of the current element
then push the current position i in stack'''
if (freq[a[stack[top]]] > freq[a[i]]):
top += 1
stack[top] = i
else:
''' If the frequency of the element which
is pointed by the top of stack is less
than frequency of the current element, then
pop the stack and continuing popping until
the above condition is true while the stack
is not empty'''
while (top > -1 and freq[a[stack[top]]] < freq[a[i]]):
res[stack[top]] = a[i]
top -= 1
# now push the current element
top += 1
stack[top] = i
'''After iterating over the loop, the remaining
position of elements in stack do not have the
next greater element, so print -1 for them'''
while (top > -1):
res[stack[top]] = -1
top -= 1
# return the res list containing next
# greater frequency element
return res
# Driver Code
print(NFG([1, 1, 2, 3, 4, 2, 1], 7))
C#
// C# program of Next Greater Frequency Element
using System;
using System.Collections;
class GFG {
/*NFG function to find the
next greater frequency
element for each element
in the array*/
static void NFG(int[] a, int n, int[] freq)
{
// stack data structure to store
// the position of array element
Stack s = new Stack();
s.Push(0);
// res to store the value of next greater
// frequency element for each element
int[] res = new int[n];
for (int i = 0; i < n; i++)
res[i] = 0;
for (int i = 1; i < n; i++)
{
/* If the frequency of the element which is
pointed by the top of stack is greater
than frequency of the current element
then Push the current position i in stack*/
if (freq[a[(int)s.Peek()]] > freq[a[i]])
s.Push(i);
else
{
/*If the frequency of the element which
is pointed by the top of stack is less
than frequency of the current element, then
Pop the stack and continuing Popping until
the above condition is true while the stack
is not empty*/
while (freq[a[(int)(int)s.Peek()]]
< freq[a[i]]
&& s.Count > 0)
{
res[(int)s.Peek()] = a[i];
s.Pop();
}
// now Push the current element
s.Push(i);
}
}
while (s.Count > 0)
{
res[(int)s.Peek()] = -1;
s.Pop();
}
for (int i = 0; i < n; i++)
{
// Print the res list containing next
// greater frequency element
Console.Write(res[i] + " ");
}
}
// Driver code
public static void Main(String[] args)
{
int[] a = { 1, 1, 2, 3, 4, 2, 1 };
int len = 7;
int max = int.MinValue;
for (int i = 0; i < len; i++)
{
// Getting the max element of the array
if (a[i] > max)
{
max = a[i];
}
}
int[] freq = new int[max + 1];
for (int i = 0; i < max + 1; i++)
freq[i] = 0;
// Calculating frequency of each element
for (int i = 0; i < len; i++)
{
freq[a[i]]++;
}
NFG(a, len, freq);
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
// Javascript program of Next Greater Frequency Element
/*NFG function to find the
next greater frequency
element for each element
in the array*/
function NFG(a, n, freq)
{
// stack data structure to store
// the position of array element
let s = [];
s.push(0);
// res to store the value of next greater
// frequency element for each element
let res = new Array(n);
for (let i = 0; i < n; i++)
res[i] = 0;
for (let i = 1; i < n; i++)
{
/* If the frequency of the element which is
pointed by the top of stack is greater
than frequency of the current element
then Push the current position i in stack*/
if (freq[a[s[s.length - 1]]] > freq[a[i]])
s.push(i);
else
{
/*If the frequency of the element which
is pointed by the top of stack is less
than frequency of the current element, then
Pop the stack and continuing Popping until
the above condition is true while the stack
is not empty*/
while (freq[a[s[s.length - 1]]]
< freq[a[i]]
&& s.length > 0)
{
res[s[s.length - 1]] = a[i];
s.pop();
}
// now Push the current element
s.push(i);
}
}
while (s.length > 0)
{
res[s[s.length - 1]] = -1;
s.pop();
}
document.write("[");
for (let i = 0; i < n - 1; i++)
{
// Print the res list containing next
// greater frequency element
document.write(res[i] + ", ");
}
document.write(res[n - 1] + "]");
}
let a = [ 1, 1, 2, 3, 4, 2, 1 ];
let len = 7;
let max = Number.MIN_VALUE;
for (let i = 0; i < len; i++)
{
// Getting the max element of the array
if (a[i] > max)
{
max = a[i];
}
}
let freq = new Array(max + 1);
for (let i = 0; i < max + 1; i++)
freq[i] = 0;
// Calculating frequency of each element
for (let i = 0; i < len; i++)
{
freq[a[i]]++;
}
NFG(a, len, freq);
// This code is contributed by vaibhavrabadiya117.
</script>
Producción
-1 -1 1 2 2 1 -1
Complejidad temporal: O(n).
Enfoque de uso eficiente del espacio: usar un mapa hash en lugar de una lista como se menciona en el enfoque anterior.
Pasos:
- Cree un par de clases para almacenar pair<int, int> con pair<elemento, frecuencia>.
- Cree un mapa hash con pares como genéricos para almacenar claves como el elemento y valores como la frecuencia de cada elemento.
- Itere la array y guarde el elemento y su frecuencia en el hashmap.
- Cree una array res que almacene la array resultante.
- Inicialmente haga res[n-1] = -1 y empuje el elemento al final junto con su frecuencia en la pila.
- Iterar a través de la array en orden inverso.
- Si la frecuencia del elemento que apunta en la parte superior de la pila es menor que la frecuencia del elemento actual y la pila no está vacía, salte.
- Continúe hasta que el ciclo falle.
- Si la pila está vacía, significa que no hay ningún elemento con una frecuencia más alta. Entonces, coloque -1 como el siguiente elemento de mayor frecuencia en la array resultante.
- Si la pila no está vacía, significa que la parte superior de la pila tiene un elemento de mayor frecuencia. Póngalo en la array resultante como la siguiente frecuencia más alta.
- Empuje el elemento actual junto con su frecuencia.
Implementación:
C++
// C++ program of Next Greater Frequency Element
#include <bits/stdc++.h>
using namespace std;
stack<pair<int,int>> mystack;
map<int, int> mymap;
/*NFG function to find the next greater frequency
element for each element and for placing it in the
resultant array */
void NGF(int arr[], int res[], int n) {
// Initially store the frequencies of all elements
// in a hashmap
for(int i = 0; i < n; i++) {
mymap[arr[i]] += 1;
}
// Get the frequency of the last element
int curr_freq = mymap[arr[n-1]];
// push it to the stack
mystack.push({arr[n-1], curr_freq});
// place -1 as next greater freq for the last
// element as it does not have next greater.
res[n-1] = -1;
// iterate through array in reverse order
for(int i = n-2;i>=0;i--) {
curr_freq = mymap[arr[i]];
/* If the frequency of the element which is
pointed by the top of stack is greater
than frequency of the current element
then push the current position i in stack*/
while(mystack.size() > 0 && curr_freq >= mystack.top().second)
mystack.pop();
// If the stack is empty, place -1. If it is not empty
// then we will have next higher freq element at the top of the stack.
res[i] = (mystack.size() == 0) ? -1 : mystack.top().first;
// push the element at current position
mystack.push({arr[i], mymap[arr[i]]});
}
}
int main()
{
int arr[] = {1, 1, 1, 2, 2, 2, 2, 11, 3, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int res[n];
NGF(arr, res, n);
cout << "[";
for(int i = 0; i < n - 1; i++)
{
cout << res[i] << ", ";
}
cout << res[n - 1] << "]";
return 0;
}
// This code is contributed by divyeshrabadiya07.
Java
// Java program of Next Greater Frequency Element
import java.util.*;
class GFG {
Stack<Pair> mystack = new Stack<>();
HashMap<Integer,Integer> mymap = new HashMap<>();
class Pair{
int data;
int freq;
Pair(int data,int freq){
this.data = data;
this.freq = freq;
}
}
/*NFG function to find the next greater frequency
element for each element and for placing it in the
resultant array */
void NGF(int[] arr,int[] res) {
int n = arr.length;
//Initially store the frequencies of all elements
//in a hashmap
for(int i = 0;i<n;i++) {
if(mymap.containsKey(arr[i]))
mymap.put(arr[i], mymap.get(arr[i]) + 1);
else
mymap.put(arr[i], 1);
}
//Get the frequency of the last element
int curr_freq = mymap.get(arr[n-1]);
//push it to the stack
mystack.push(new Pair(arr[n-1],curr_freq));
//place -1 as next greater freq for the last
//element as it does not have next greater.
res[n-1] = -1;
//iterate through array in reverse order
for(int i = n-2;i>=0;i--) {
curr_freq = mymap.get(arr[i]);
/* If the frequency of the element which is
pointed by the top of stack is greater
than frequency of the current element
then push the current position i in stack*/
while(!mystack.isEmpty() && curr_freq >= mystack.peek().freq)
mystack.pop();
//If the stack is empty, place -1. If it is not empty
//then we will have next higher freq element at the top of the stack.
res[i] = (mystack.isEmpty()) ? -1 : mystack.peek().data;
//push the element at current position
mystack.push(new Pair(arr[i],mymap.get(arr[i])));
}
}
//Driver function
public static void main(String args[]) {
GFG obj = new GFG();
int[] arr = {1, 1, 1, 2, 2, 2, 2, 11, 3, 3};
int res[] = new int[arr.length];
obj.NGF(arr, res);
System.out.println(Arrays.toString(res));
}
}
//This method is contributed by Likhita AVL
Python3
# Python3 program of Next Greater Frequency Element
mystack = []
mymap = {}
"""NFG function to find the next greater frequency
element for each element and for placing it in the
resultant array """
def NGF(arr, res):
n = len(arr)
# Initially store the frequencies of all elements
# in a hashmap
for i in range(n):
if arr[i] in mymap:
mymap[arr[i]] += 1
else:
mymap[arr[i]] = 1
# Get the frequency of the last element
curr_freq = mymap[arr[n-1]]
# push it to the stack
mystack.append([arr[n-1],curr_freq])
# place -1 as next greater freq for the last
# element as it does not have next greater.
res[n-1] = -1
# iterate through array in reverse order
for i in range(n - 2, -1, -1):
curr_freq = mymap[arr[i]]
""" If the frequency of the element which is
pointed by the top of stack is greater
than frequency of the current element
then push the current position i in stack"""
while len(mystack) > 0 and curr_freq >= mystack[-1][1]:
mystack.pop()
# If the stack is empty, place -1. If it is not empty
# then we will have next higher freq element at the top of the stack.
if (len(mystack) == 0):
res[i] = -1
else:
res[i] = mystack[-1][0]
# push the element at current position
mystack.append([arr[i],mymap[arr[i]]])
arr = [1, 1, 1, 2, 2, 2, 2, 11, 3, 3]
res = [0]*(len(arr))
NGF(arr, res)
print(res)
# This code is contributed by rameshtravel07.
C#
// C# program of Next Greater Frequency Element
using System;
using System.Collections.Generic;
class GFG {
static Stack<Tuple<int,int>> mystack = new Stack<Tuple<int,int>>();
static Dictionary<int, int> mymap = new Dictionary<int, int>();
/*NFG function to find the next greater frequency
element for each element and for placing it in the
resultant array */
static void NGF(int[] arr,int[] res) {
int n = arr.Length;
// Initially store the frequencies of all elements
// in a hashmap
for(int i = 0; i < n; i++) {
if(mymap.ContainsKey(arr[i]))
mymap[arr[i]] = mymap[arr[i]] + 1;
else
mymap[arr[i]] = 1;
}
// Get the frequency of the last element
int curr_freq = mymap[arr[n-1]];
// push it to the stack
mystack.Push(new Tuple<int,int>(arr[n-1],curr_freq));
// place -1 as next greater freq for the last
// element as it does not have next greater.
res[n-1] = -1;
// iterate through array in reverse order
for(int i = n-2;i>=0;i--) {
curr_freq = mymap[arr[i]];
/* If the frequency of the element which is
pointed by the top of stack is greater
than frequency of the current element
then push the current position i in stack*/
while(mystack.Count > 0 && curr_freq >= mystack.Peek().Item2)
mystack.Pop();
// If the stack is empty, place -1. If it is not empty
// then we will have next higher freq element at the top of the stack.
res[i] = (mystack.Count == 0) ? -1 : mystack.Peek().Item1;
// push the element at current position
mystack.Push(new Tuple<int,int>(arr[i],mymap[arr[i]]));
}
}
// Driver code
static void Main() {
int[] arr = {1, 1, 1, 2, 2, 2, 2, 11, 3, 3};
int[] res = new int[arr.Length];
NGF(arr, res);
Console.Write("[");
for(int i = 0; i < arr.Length - 1; i++)
{
Console.Write(res[i] + ", ");
}
Console.Write(res[arr.Length - 1] + "]");
}
}
// This code is contributed by mukesh07.
Javascript
<script>
// Javascript program of Next Greater Frequency Element
class Pair
{
constructor(data,freq)
{
this.data = data;
this.freq = freq;
}
}
let mystack = [];
let mymap = new Map();
/*NFG function to find the next greater frequency
element for each element and for placing it in the
resultant array */
function NGF(arr,res)
{
let n = arr.length;
//Initially store the frequencies of all elements
//in a hashmap
for(let i = 0;i<n;i++) {
if(mymap.has(arr[i]))
mymap.set(arr[i], mymap.get(arr[i]) + 1);
else
mymap.set(arr[i], 1);
}
// Get the frequency of the last element
let curr_freq = mymap.get(arr[n-1]);
// push it to the stack
mystack.push(new Pair(arr[n-1],curr_freq));
// place -1 as next greater freq for the last
// element as it does not have next greater.
res[n-1] = -1;
// iterate through array in reverse order
for(let i = n - 2; i >= 0; i--)
{
curr_freq = mymap.get(arr[i]);
/* If the frequency of the element which is
pointed by the top of stack is greater
than frequency of the current element
then push the current position i in stack*/
while(mystack.length!=0 && curr_freq >= mystack[mystack.length-1].freq)
mystack.pop();
// If the stack is empty, place -1. If it is not empty
// then we will have next higher freq element at the top of the stack.
res[i] = (mystack.length==0) ? -1 : mystack[mystack.length-1].data;
// push the element at current position
mystack.push(new Pair(arr[i],mymap.get(arr[i])));
}
}
// Driver function
let arr=[1, 1, 1, 2, 2, 2, 2, 11, 3, 3];
let res = new Array(arr.length);
NGF(arr, res);
document.write((res).join(" "));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
[2, 2, 2, -1, -1, -1, -1, 3, -1, -1]
Complejidad temporal: O(n).
Este artículo es una contribución de Sruti Rai . Gracias Koustav por su valioso apoyo. 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