Dada una array arr[] de tamaño N , y Q consultas de la forma {i, k} para las cuales, la tarea es imprimir el elemento más frecuente en la array después de reemplazar arr[i] por k .
Ejemplo :
Entrada: arr[] = {2, 2, 2, 3, 3}, Consulta = {{0, 3}, {4, 2}, {0, 4}}
Salida: 3 2 2
Primera consulta: Configuración de arr[ 0] = 3 modifica arr[] = {3, 2, 2, 3, 3}. Entonces, 3 tiene una frecuencia máxima.
Segunda consulta: Establecer arr[4] = 2, modifica arr[] = {3, 2, 2, 3, 2}. Entonces, 2 tiene una frecuencia máxima.
Tercera consulta: Establecer arr[0] = 4, modifica arr[] = {4, 2, 2, 3, 2}. Entonces, 2 tiene la frecuencia máxima
Entrada: arr[] = {1, 2, 3, 4, 3, 3} Consulta = {{0, 2}, {3, 2}, {2, 4}}
Salida: 3 2 2
Enfoque ingenuo:
para cada consulta, reemplace arr[i] por K, recorra toda la array y cuente la frecuencia de cada elemento de la array e imprima los más frecuentes.
Complejidad de tiempo: O(N * Q)
Espacio auxiliar: O(N)
Enfoque eficiente:
El enfoque anterior se puede optimizar calculando previamente las frecuencias de cada elemento del arreglo y manteniendo los pares de elementos del arreglo de frecuencia en un conjunto para obtener el elemento más frecuente en O(1). Siga los pasos a continuación para resolver el problema:
- Inicialice un mapa para almacenar las frecuencias de todos los elementos de la array y un conjunto de pares para almacenar los pares de elementos de frecuencia. En el conjunto, almacene las frecuencias como negativas. Esto asegura que el primer par almacenado al comienzo del conjunto, es decir, s.begin(), es el emparejamiento {-(frecuencia máxima), elemento más frecuente} .
- Para cada consulta, mientras elimina el elemento de la array en el i -ésimo índice, realice las siguientes tareas:
- Encuentre la frecuencia de arr[i] del mapa, es decir mp[arr[i]].
- Elimina el par {-mp[arr[i]], arr[i]} del conjunto.
- Actualice el conjunto después de disminuir la frecuencia de arr[i] insertando {-(mp[arr[i] – 1), arr[i]} en el conjunto.
- Disminuya la frecuencia de arr[i] en el mapa.
- Para insertar K en la array para cada consulta, haga lo siguiente:
- Encuentre la frecuencia de K del mapa, es decir, mp[K] .
- Retire el par {-mp[K], K} del conjunto.
- Actualice el conjunto después de aumentar la frecuencia de K insertando {-(mp[K] + 1), K} en el conjunto.
- Aumenta la frecuencia de K en el mapa.
- Finalmente, para cada consulta, extraiga el par al comienzo del conjunto. El primer elemento del conjunto denota -(frecuencia máxima) . Por lo tanto, el segundo elemento será el elemento más frecuente. Imprime el segundo elemento del par.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the most
// frequent element after every
// update query on the array
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
// Function to print the most
// frequent element of array
// along with update query
void mostFrequent(ll arr[], ll n, ll m,
vector<vector<ll> > q)
{
ll i;
// Stores element->frequencies
// mappings
map<ll, ll> mp;
for (i = 0; i < n; i++)
mp[arr[i]] += 1;
// Stores frequencies->element
// mappings
set<pair<ll, ll> > s;
// Store the frequencies in
// negative
for (auto it : mp) {
s.insert(make_pair(-(it.second),
it.first));
}
for (i = 0; i < m; i++) {
// Index to be modified
ll j = q[i][0];
// Value to be inserted
ll k = q[i][1];
// Store the frequency of
// arr[j] and k
auto it = mp.find(arr[j]);
auto it2 = mp.find(k);
// Remove mapping of arr[j]
// with previous frequency
s.erase(make_pair(-(it->second),
it->first));
// Update mapping with new
// frequency
s.insert(make_pair(-((it->second)
- 1),
it->first));
// Update frequency of arr[j]
// in the map
mp[arr[j]]--;
// Remove mapping of k
// with previous frequency
s.erase(make_pair(-(it2->second),
it2->first));
// Update mapping of k
// with previous frequency
s.insert(make_pair(-((it2->second)
+ 1),
it2->first));
// Update frequency of k
mp[k]++;
// Replace arr[j] by k
arr[j] = k;
// Display maximum frequent element
cout << (*s.begin()).second << " ";
}
}
// Driver Code
int main()
{
ll i, N, Q;
N = 5;
Q = 3;
ll arr[] = { 2, 2, 2, 3, 3 };
vector<vector<ll> > query = {
{ 0, 3 },
{ 4, 2 },
{ 0, 4 }
};
mostFrequent(arr, N, Q, query);
}
Java
// Java program to find the most
// frequent element after every
// update query on the array
import java.util.*;
import java.io.*;
class GFG{
// Pair class represents
// a pair of elements
static class Pair
{
int first, second;
Pair(int f,int s)
{
first = f;
second = s;
}
}
// Function to print the most
// frequent element of array
// along with update query
static void mostFrequent(int arr[], int n, int m,
ArrayList<Pair> q)
{
int i;
// Stores element->frequencies
// mappings
HashMap<Integer, Integer> map = new HashMap<>();
HashMap<Integer, Pair> map1 = new HashMap<>();
for(i = 0; i < n; i++)
{
if(!map.containsKey(arr[i]))
map.put(arr[i], 1);
else
map.put(arr[i], map.get(arr[i]) + 1);
}
// Stores frequencies->element
// mappings
TreeSet<Pair> set = new TreeSet<>(
new Comparator<Pair>()
{
public int compare(Pair p1, Pair p2)
{
return p2.first - p1.first;
}
});
// Store the frequencies in
// bigger to smaller
for(Map.Entry<Integer,
Integer> entry : map.entrySet())
{
Pair p = new Pair(entry.getValue(),
entry.getKey());
set.add(p);
map1.put(entry.getKey(), p);
}
for(i = 0; i < m; i++)
{
// Index to be modified
int j = q.get(i).first;
// Value to be inserted
int k = q.get(i).second;
// Insert the new Pair
// with value k if it was
// not inserted
if(map1.get(k) == null)
{
Pair p = new Pair(0, k);
map1.put(k, p);
set.add(p);
}
// Get the Pairs of
// arr[j] and k
Pair p1 = map1.get(arr[j]);
set.remove(p1);
Pair p2 = map1.get(k);
set.remove(p2);
// Decrease the frequency of
// mapping with value arr[j]
p1.first--;
set.add(p1);
// Update frequency of arr[j]
// in the map
map.put(arr[j], map.get(arr[j]) - 1);
// Increase the frequency of
// mapping with value k
p2.first++;
set.add(p2);
// Update frequency of k
if(map.containsKey(k))
map.put(k, map.get(k) + 1);
else
map.put(k, 1);
// Replace arr[j] by k
arr[j] = k;
// Display maximum frequent element
System.out.print(
set.iterator().next().second + " ");
}
}
// Driver Code
public static void main(String []args)
{
int i, N, Q;
N = 5;
Q = 3;
int arr[] = { 2, 2, 2, 3, 3 };
ArrayList<Pair> query = new ArrayList<>();
query.add(new Pair(0, 3));
query.add(new Pair(4, 2));
query.add(new Pair(0, 4));
mostFrequent(arr, N, Q, query);
}
}
// This code is contributed by Ganeshchowdharysadanala
Python3
# Python program to find the most # frequent element after every # update query on the array from typing import List from collections import defaultdict # Function to print the most # frequent element of array # along with update query def mostFrequent(arr: List[int], n: int, m: int, q: List[List[int]]) -> None: i = 0 # Stores element->frequencies # mappings mp = defaultdict(lambda: 0) for i in range(n): mp[arr[i]] += 1 # Stores frequencies->element # mappings s = set() # Store the frequencies in # negative for k, v in mp.items(): s.add((-v, k)) for i in range(m): # Index to be modified j = q[i][0] # Value to be inserted k = q[i][1] # Store the frequency of # arr[j] and k it = mp[arr[j]] it2 = mp[k] # Remove mapping of arr[j] # with previous frequency if (-it, arr[j]) in s: s.remove((-it, arr[j])) # Update mapping with new # frequency s.add((-(it - 1), arr[j])) # Update frequency of arr[j] # in the map mp[arr[j]] -= 1 # Remove mapping of k # with previous frequency if (-it2, k) in s: s.remove((-it2, k)) # Update mapping of k # with previous frequency s.add((-(it2 + 1), k)) # Update frequency of k mp[k] += 1 # Replace arr[j] by k arr[j] = k # Display maximum frequent element print(sorted(s)[0][1]) # Driver Code if __name__ == "__main__": N = 5 Q = 3 arr = [2, 2, 2, 3, 3] query = [[0, 3], [4, 2], [0, 4]] mostFrequent(arr, N, Q, query) # This code is contributed by sanjeev2552
Producción:
3 2 2
Complejidad temporal: O(N + (Q * LogN))
Espacio auxiliar: O(N)