Dada una array arr[] de N enteros y una array Q[] de M pares, donde un par representa una consulta de la forma {L, R}, la tarea es encontrar el elemento máximo que aparece en el rango [L, R] y su frecuencia para cada consulta. Si hay varios elementos con la frecuencia máxima, imprima el elemento máximo entre ellos.
Ejemplos:
Entrada: arr[] = {5, 7, 5, 5, 2, 7, 3, 2, 5, 2}, Q[] = {{0, 9}, {3, 6}, {4, 8} , {1, 5}}
Salida: 5 Ocurre 4 veces
3 Ocurre 1 vez
2 Ocurre 2 veces
7 Ocurre 2 veces
Explicación:
Las consultas se realizan como:
- Consulta (0, 9): el subarreglo sobre el rango es {5, 7, 5, 5, 2, 7, 3, 2, 5, 2}. Los elementos 5, 7, 2 y 3 ocurren 4, 2, 3 y 1 veces respectivamente. Por lo tanto, imprime 5.
- Consulta (3, 6): el subarreglo sobre el rango es {5, 2, 7, 3}. Cada elemento ocurre una vez. Entonces imprima el elemento 7.
- Consulta (4, 8): el subarreglo sobre el rango es {2, 7, 3, 2, 5}. El elemento 2 ocurre dos veces y el resto ocurre una vez. Por lo tanto, imprime 2.
- Consulta (1, 5): el subarreglo sobre el rango es {7, 5, 5, 2, 7, 3}. Los elementos 7 y 5 ocurren dos veces y los elementos restantes ocurren una vez. Por lo tanto imprime 7.
Enfoque ingenuo: para cada consulta, itere sobre el rango dado [L, R] y siga actualizando la frecuencia de cada elemento en una estructura de datos auxiliar (por ejemplo, mapa ). Después de procesar todo el rango de la consulta actual, itere sobre todos los elementos en el mapa y encuentre el elemento que tiene la frecuencia máxima .
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 find the elements having
// maximum frequency for the query range
void getMaxOccuringElement(int arr[], int N, int M,
pair<int, int> Q[])
{
// Iterate over all the queries
for (int i = 0; i < M; ++i) {
// Stores the frequency of each element
// in the current query range [l, r]
map<int, int> freq;
int l = Q[i].first, r = Q[i].second;
for (int j = l; j <= r; ++j)
++freq[arr[j]];
int maxFreqElement = -1;
int maxFreq = -1;
// Iterate over the map and find the
// element having maximum frequency
for (auto it : freq) {
if (it.second >= maxFreq) {
maxFreqElement = it.first;
maxFreq = it.second;
}
}
// Print the answer for current query
cout << maxFreqElement << " Occurs " << maxFreq
<< " times" << endl;
}
}
// Driver Code
int main()
{
int arr[] = { 5, 7, 5, 5, 2, 7, 3, 2, 5, 2 };
pair<int, int> Q[]
= { { 0, 9 }, { 3, 6 }, { 4, 8 }, { 1, 5 } };
int N = sizeof(arr) / sizeof(arr[0]);
int M = sizeof(Q) / sizeof(Q[0]);
getMaxOccuringElement(arr, N, M, Q);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to find the elements having
// maximum frequency for the query range
static void getMaxOccuringElement(int arr[], int N, int M,
pair Q[])
{
// Iterate over all the queries
for (int i = 0; i < M; ++i) {
// Stores the frequency of each element
// in the current query range [l, r]
HashMap<Integer,Integer> freq = new HashMap<Integer,Integer>();
int l = Q[i].first, r = Q[i].second;
for (int j = l; j <= r; ++j) {
if(freq.containsKey(arr[j]))
freq.put(arr[j], freq.get(arr[j])+1);
else
freq.put(arr[j], 1);
}
int maxFreqElement = -1;
int maxFreq = -1;
// Iterate over the map and find the
// element having maximum frequency
for (Map.Entry<Integer,Integer> it : freq.entrySet()) {
if (it.getValue() >= maxFreq) {
maxFreqElement = it.getKey();
maxFreq = it.getValue();
}
}
// Print the answer for current query
System.out.print(maxFreqElement+ " Occurs " + maxFreq
+ " times" +"\n");
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 5, 7, 5, 5, 2, 7, 3, 2, 5, 2 };
pair Q[]
= { new pair( 0, 9 ), new pair( 3, 6 ), new pair( 4, 8 ), new pair( 1, 5 ) };
int N = arr.length;
int M = Q.length;
getMaxOccuringElement(arr, N, M, Q);
}
}
// This code contributed by Princi Singh
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to find the elements having
// maximum frequency for the query range
static void getMaxOccuringElement(int []arr, int N, int M,
pair []Q)
{
// Iterate over all the queries
for (int i = 0; i < M; ++i) {
// Stores the frequency of each element
// in the current query range [l, r]
Dictionary<int,int> freq = new Dictionary<int,int>();
int l = Q[i].first, r = Q[i].second;
for (int j = l; j <= r; ++j) {
if(freq.ContainsKey(arr[j]))
freq[arr[j]] = freq[arr[j]]+1;
else
freq.Add(arr[j], 1);
}
int maxFreqElement = -1;
int maxFreq = -1;
// Iterate over the map and find the
// element having maximum frequency
foreach (KeyValuePair<int,int> it in freq) {
if (it.Value >= maxFreq) {
maxFreqElement = it.Key;
maxFreq = it.Value;
}
}
// Print the answer for current query
Console.Write(maxFreqElement+ " Occurs " + maxFreq
+ " times" +"\n");
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 5, 7, 5, 5, 2, 7, 3, 2, 5, 2 };
pair []Q
= { new pair( 0, 9 ), new pair( 3, 6 ), new pair( 4, 8 ), new pair( 1, 5 ) };
int N = arr.Length;
int M = Q.Length;
getMaxOccuringElement(arr, N, M, Q);
}
}
// This code is contributed by 29AjayKumar
Producción
5 Occurs 4 times 7 Occurs 1 times 2 Occurs 2 times 7 Occurs 2 times
Complejidad temporal: O(M * N)
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior puede optimizarse mediante el algoritmo de Mo basado en el concepto de descomposición sqrt. Siga los pasos a continuación para resolver el problema:
- Las consultas se ordenan en orden no decreciente de los bloques en los que cae su índice izquierdo. Si dos o más consultas tienen sus índices izquierdos en el mismo bloque, ordénelas según sus índices derechos .
- Básicamente, calcula la respuesta para todas las consultas que tienen su índice izquierdo en el bloque 0, luego el bloque 1, y así sucesivamente hasta el último bloque.
- Mantenga una estructura de datos de mapa ( num_freq ) que almacene el recuento de ocurrencias de cada elemento en el rango de consulta actual .
- Además, mantenga una estructura de datos establecida ( freq_num ), en la que cada elemento sea un par (el primer elemento del par representa el recuento de ocurrencias de un elemento y el segundo elemento del par representa el elemento en sí).
- El conjunto ( freq_num ) almacena los elementos en orden no decreciente . El orden de los elementos del conjunto se basa en el primer elemento del par , que representa la frecuencia .
- Por lo tanto, al responder a las consultas (es decir, el elemento que tiene la frecuencia máxima), se puede hacer en O(1) .
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;
int BLOCK_SIZE;
// Structure to represent a query range
// and its index
struct query {
int l, r, idx;
};
// Custom comparator
bool comparator(query a, query b)
{
if ((a.l / BLOCK_SIZE) != (b.l / BLOCK_SIZE))
return (a.l / BLOCK_SIZE) < (b.l / BLOCK_SIZE);
return ((a.l / BLOCK_SIZE) & 1) ? (a.r < b.r)
: (a.r > b.r);
}
// Function to add elements to the current range
void expand(int idx, int* arr, map<int, int>& numFreq,
set<pair<int, int> >& freqNum)
{
// Remove current element from the set
freqNum.erase({ numFreq[arr[idx]], arr[idx] });
// Increment current element count in the
// map
++numFreq[arr[idx]];
// Insert current element into the set
freqNum.insert({ numFreq[arr[idx]], arr[idx] });
}
// Function to remove elements from the current range
void shrink(int idx, int* arr, map<int, int>& numFreq,
set<pair<int, int> >& freqNum)
{
// Remove current element from the set
freqNum.erase({ numFreq[arr[idx]], arr[idx] });
// Decrement current element count in the
// map
--numFreq[arr[idx]];
// Insert current element into the set
freqNum.insert({ numFreq[arr[idx]], arr[idx] });
}
// Function for Mo's algorithm
pair<int, int>
sqrtDecomposition(int& L, int& R, int l, int r, int* arr,
set<pair<int, int> >& freqNum,
map<int, int>& numFreq)
{
// Iterate until L is greater than l
while (L > l) {
--L;
expand(L, arr, numFreq, freqNum);
}
// Iterate until R is less than r
while (R < r) {
++R;
expand(R, arr, numFreq, freqNum);
}
// Iterate until L is less than l
while (L < l) {
shrink(L, arr, numFreq, freqNum);
++L;
}
// Iterate until R is greater than r
while (R > r) {
shrink(R, arr, numFreq, freqNum);
--R;
}
// Stores the answer for current query
pair<int, int> last = *prev(freqNum.end());
// Return the answer
return last;
}
// Function to find the element having maximum
// frequency and its frequency for all the queries
void getMaxOccuringElement(int arr[], int N, int M,
pair<int, int> Q[])
{
// Compute each block size
BLOCK_SIZE = (int)sqrt(N + .0) + 1;
// Stores the queries
query queries[M];
for (int i = 0; i < M; ++i) {
queries[i].l = Q[i].first;
queries[i].r = Q[i].second;
queries[i].idx = i;
}
// Sort all the queries
sort(queries, queries + M, comparator);
// Initiali ranges of Mos
int L = 0, R = -1;
// Stores the answer
pair<int, int> ans[M];
set<pair<int, int> > freqNum;
map<int, int> numFreq;
// Traverse the query array
for (int i = 0; i < M; ++i) {
int l = queries[i].l;
int r = queries[i].r;
// Stores the answer for current
// query
ans[queries[i].idx] = sqrtDecomposition(
L, R, l, r, arr, freqNum, numFreq);
}
// Print the answer
for (int i = 0; i < M; ++i) {
cout << ans[i].second << " Occurs " << ans[i].first
<< " times" << endl;
}
}
// Driver Code
int main()
{
int arr[] = { 5, 7, 5, 5, 2, 7, 3, 2, 5, 2 };
pair<int, int> Q[]
= { { 0, 9 }, { 3, 6 }, { 4, 8 }, { 1, 5 } };
int N = sizeof(arr) / sizeof(arr[0]);
int M = sizeof(Q) / sizeof(Q[0]);
getMaxOccuringElement(arr, N, M, Q);
return 0;
}
Producción
5 Occurs 4 times 7 Occurs 1 times 2 Occurs 2 times 7 Occurs 2 times
Complejidad de tiempo: O((N+M) * log(N) * sqrt(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por tridib_samanta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA