Dada una array de n enteros en orden no decreciente. Encuentre el número de ocurrencias del valor más frecuente dentro de un rango dado.
Ejemplos:
Input : arr[] = {-5, -5, 2, 2, 2, 2, 3, 7, 7, 7}
Query 1: start = 0, end = 9
Query 2: start = 4, end = 9
Output : 4
3
Explanation:
Query 1: '2' occurred the most number of times
with a frequency of 4 within given range.
Query 2: '7' occurred the most number of times
with a frequency of 3 within given range.
Los árboles de segmentos se pueden utilizar para resolver este problema de manera eficiente.
Consulte aquí para la implementación de árboles de segmentos.
La idea clave detrás de este problema es que la array dada está en orden no decreciente, lo que significa que todas las ocurrencias de un número se colocan consecutivamente en la array, ya que la array está ordenada.
Se puede construir un árbol de segmentos donde cada Node almacenaría el recuento máximo de su rango respectivo [i, j]. Para eso construiremos la array de frecuencias y llamaremos RMQ (Range Maximum Query) en esta array. Por ejemplo
arr[] = {-5, -5, 2, 2, 2, 2, 3, 7, 7, 7}
freq_arr[] = {2, 2, 4, 4, 4, 4, 1, 3, 3, 3}
where, freq_arr[i] = frequency(arr[i])
Ahora hay que considerar dos casos,
Caso 1: El valor de los números en el índice iyj para el rango dado es el mismo, es decir, arr[i] = arr[j].
Resolver este caso es muy fácil. Dado que arr[i] = arr[j], todos los números entre estos índices son iguales (ya que la array no es decreciente). Por lo tanto, la respuesta para este caso es simplemente contar todos los números entre i y j (ambos incluidos), es decir, (j – i + 1)
Por ejemplo
arr[] = {-5, -5, 2, 2, 2, 2, 3, 7, 7, 7}
if the given query range is [3, 5], answer would
be (5 - 3 + 1) = 3, as 2 occurs 3 times within
given range
Caso 2: El valor de los números en el índice i y j para el rango dado son diferentes, es decir, arr[i] != arr[j]
Si arr[i] != arr[j], entonces existe un índice k donde arr[i] = arr[k] y arr[i] != arr[k + 1]. Este puede ser un caso de superposición parcial donde algunas apariciones de un número en particular se encuentran en la parte más a la izquierda del rango dado y algunas se encuentran justo antes de que comience el rango. Aquí simplemente llamar a RMQ daría como resultado una respuesta incorrecta.
Por ejemplo
arr[] = {-5, -5, 2, 2, 2, 2, 3, 7, 7, 7}
freq_arr[] = {2, 2, 4, 4, 4, 4, 1, 3, 3, 3}
if the given query is [4, 9], calling RMQ on
freq_arr[] will give us 4 as answer which
is incorrect as some occurrences of 2 are
lying outside the range. Correct answer
is 3.
Una situación similar puede ocurrir en la parte más a la derecha del rango dado donde algunas apariciones de un número en particular se encuentran dentro del rango y otras se encuentran justo después de que termina el rango.
Por lo tanto, para este caso, dentro del rango dado, tenemos que contar los mismos números más a la izquierda hasta algún índice, digamos i, y los mismos números más a la derecha desde el índice, digamos j hasta el final del rango. Y luego llamando a RMQ (Range Maximum Query) entre los índices i y j y tomando el máximo de estos tres.
Por ejemplo
arr[] = {-5, -5, 2, 2, 2, 2, 3, 7, 7, 7}
freq_arr[] = {2, 2, 4, 4, 4, 4, 1, 3, 3, 3}
if the given query is [4, 7], counting leftmost
same numbers i.e 2 which occurs 2 times inside
the range and rightmost same numbers i.e. 3
which occur only 1 time and RMQ on [6, 6] is
1. Hence maximum would be 2.
A continuación se muestra la implementación del enfoque anterior.
CPP
// C++ Program to find the occurrence
// of the most frequent number within
// a given range
#include <bits/stdc++.h>
using namespace std;
// A utility function to get the middle index
// from corner indexes.
int getMid(int s, int e) { return s + (e - s) / 2; }
/* A recursive function to get the maximum value in
a given range of array indexes. The following
are parameters for this function.
st --> Pointer to segment tree
index --> Index of current node in the segment
tree. Initially 0 is passed as root is
always at index 0
ss & se --> Starting and ending indexes of the
segment represented by current node,
i.e., st[index]
qs & qe --> Starting and ending indexes of query
range */
int RMQUtil(int* st, int ss, int se, int qs, int qe,
int index)
{
// If segment of this node is a part of given range,
// then return the min of the segment
if (qs <= ss && qe >= se)
return st[index];
// If segment of this node is outside the
// given range
if (se < qs || ss > qe)
return 0;
// If a part of this segment overlaps
// with the given range
int mid = getMid(ss, se);
return max(RMQUtil(st, ss, mid, qs, qe, 2 * index + 1),
RMQUtil(st, mid + 1, se, qs, qe, 2 * index + 2));
}
// Return minimum of elements in range from
// index qs (query start) to
// qe (query end). It mainly uses RMQUtil()
int RMQ(int* st, int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n - 1 || qs > qe) {
printf("Invalid Input");
return -1;
}
return RMQUtil(st, 0, n - 1, qs, qe, 0);
}
// A recursive function that constructs Segment Tree
// for array[ss..se]. si is index of current node in
// segment tree st
int constructSTUtil(int arr[], int ss, int se, int* st,
int si)
{
// If there is one element in array, store it in
// current node of segment tree and return
if (ss == se) {
st[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements, then
// recur for left and right subtrees and store
// the minimum of two values in this node
int mid = getMid(ss, se);
st[si] = max(constructSTUtil(arr, ss, mid, st, si * 2 + 1),
constructSTUtil(arr, mid + 1, se, st, si * 2 + 2));
return st[si];
}
/* Function to construct segment tree from given
array. This function allocates memory for segment
tree and calls constructSTUtil() to fill the
allocated memory */
int* constructST(int arr[], int n)
{
// Allocate memory for segment tree
// Height of segment tree
int x = (int)(ceil(log2(n)));
// Maximum size of segment tree
int max_size = 2 * (int)pow(2, x) - 1;
int* st = new int[max_size];
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0);
// Return the constructed segment tree
return st;
}
int maximumOccurrence(int arr[], int n, int qs, int qe)
{
// Declaring a frequency array
int freq_arr[n + 1];
// Counting frequencies of all array elements.
unordered_map<int, int> cnt;
for (int i = 0; i < n; i++)
cnt[arr[i]]++;
// Creating frequency array by replacing the
// number in array to the number of times it
// has appeared in the array
for (int i = 0; i < n; i++)
freq_arr[i] = cnt[arr[i]];
// Build segment tree from this frequency array
int* st = constructST(freq_arr, n);
int maxOcc; // to store the answer
// Case 1: numbers are same at the starting
// and ending index of the query
if (arr[qs] == arr[qe])
maxOcc = (qe - qs + 1);
// Case 2: numbers are different
else {
int leftmost_same = 0, righmost_same = 0;
// Partial Overlap Case of a number with some
// occurrences lying inside the leftmost
// part of the range and some just before the
// range starts
while (qs > 0 && qs <= qe && arr[qs] == arr[qs - 1]) {
qs++;
leftmost_same++;
}
// Partial Overlap Case of a number with some
// occurrences lying inside the rightmost part of
// the range and some just after the range ends
while (qe >= qs && qe < n - 1 && arr[qe] == arr[qe + 1]) {
qe--;
righmost_same++;
}
// Taking maximum of all three
maxOcc = max({leftmost_same, righmost_same,
RMQ(st, n, qs, qe)});
}
return maxOcc;
}
// Driver Code
int main()
{
int arr[] = { -5, -5, 2, 2, 2, 2, 3, 7, 7, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
int qs = 0; // Starting index of query range
int qe = 9; // Ending index of query range
// Print occurrence of most frequent number
// within given range
cout << "Maximum Occurrence in range is = "
<< maximumOccurrence(arr, n, qs, qe) << endl;
qs = 4; // Starting index of query range
qe = 9; // Ending index of query range
// Print occurrence of most frequent number
// within given range
cout << "Maximum Occurrence in range is = "
<< maximumOccurrence(arr, n, qs, qe) << endl;
return 0;
}
Python3
# Python 3 Program to find the occurrence
# of the most frequent number within
# a given range
from collections import defaultdict
import math
# A utility function to get the middle index
# from corner indexes.
def getMid(s, e):
return s + (e - s) // 2
''' A recursive function to get the maximum value in
a given range of array indexes. The following
are parameters for this function.
st --> Pointer to segment tree
index --> Index of current node in the segment
tree. Initially 0 is passed as root is
always at index 0
ss & se --> Starting and ending indexes of the
segment represented by current node,
i.e., st[index]
qs & qe --> Starting and ending indexes of query
range '''
def RMQUtil(st, ss, se, qs, qe, index):
# If segment of this node is a part of given range
# then return the min of the segment
if (qs <= ss and qe >= se):
return st[index]
# If segment of this node is outside the
# given range
if (se < qs or ss > qe):
return 0
# If a part of this segment overlaps
# with the given range
mid = getMid(ss, se)
return max(RMQUtil(st, ss, mid, qs, qe, 2 * index + 1),
RMQUtil(st, mid + 1, se, qs, qe, 2 * index + 2))
# Return minimum of elements in range from
# index qs (query start) to
# qe (query end). It mainly uses RMQUtil()
def RMQ(st, n, qs, qe):
# Check for erroneous input values
if (qs < 0 or qe > n - 1 or qs > qe):
prf("Invalid Input")
return -1
return RMQUtil(st, 0, n - 1, qs, qe, 0)
# A recursive function that constructs Segment Tree
# for array[ss..se]. si is index of current node in
# segment tree st
def constructSTUtil(arr, ss, se, st,
si):
# If there is one element in array, store it in
# current node of segment tree and return
if (ss == se):
st[si] = arr[ss]
return arr[ss]
# If there are more than one elements, then
# recur for left and right subtrees and store
# the minimum of two values in this node
mid = getMid(ss, se)
st[si] = max(constructSTUtil(arr, ss, mid, st, si * 2 + 1),
constructSTUtil(arr, mid + 1, se, st, si * 2 + 2))
return st[si]
''' Function to construct segment tree from given
array. This function allocates memory for segment
tree and calls constructSTUtil() to fill the
allocated memory '''
def constructST(arr, n):
# Allocate memory for segment tree
# Height of segment tree
x = (math.ceil(math.log2(n)))
# Maximum size of segment tree
max_size = 2 * pow(2, x) - 1
st = [0]*max_size
# Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0)
# Return the constructed segment tree
return st
def maximumOccurrence(arr, n, qs, qe):
# Declaring a frequency array
freq_arr = [0]*(n + 1)
# Counting frequencies of all array elements.
cnt = defaultdict(int)
for i in range(n):
cnt[arr[i]] += 1
# Creating frequency array by replacing the
# number in array to the number of times it
# has appeared in the array
for i in range(n):
freq_arr[i] = cnt[arr[i]]
# Build segment tree from this frequency array
st = constructST(freq_arr, n)
maxOcc = 0 # to store the answer
# Case 1: numbers are same at the starting
# and ending index of the query
if (arr[qs] == arr[qe]):
maxOcc = (qe - qs + 1)
# Case 2: numbers are different
else:
leftmost_same = 0
righmost_same = 0
# Partial Overlap Case of a number with some
# occurrences lying inside the leftmost
# part of the range and some just before the
# range starts
while (qs > 0 and qs <= qe and arr[qs] == arr[qs - 1]):
qs += 1
leftmost_same += 1
# Partial Overlap Case of a number with some
# occurrences lying inside the rightmost part of
# the range and some just after the range ends
while (qe >= qs and qe < n - 1 and arr[qe] == arr[qe + 1]):
qe -= 1
righmost_same += 1
# Taking maximum of all three
maxOcc = max([leftmost_same, righmost_same,
RMQ(st, n, qs, qe)])
return maxOcc
# Driver Code
if __name__ == "__main__":
arr = [-5, -5, 2, 2, 2, 2, 3, 7, 7, 7]
n = len(arr)
qs = 0 # Starting index of query range
qe = 9 # Ending index of query range
# Print occurrence of most frequent number
# within given range
print("Maximum Occurrence in range is = ",
maximumOccurrence(arr, n, qs, qe))
qs = 4 # Starting index of query range
qe = 9 # Ending index of query range
# Print occurrence of most frequent number
# within given range
print("Maximum Occurrence in range is = ",
maximumOccurrence(arr, n, qs, qe))
# This code is contributed by ukasp.
Maximum Occurrence in range is = 4 Maximum Occurrence in range is = 3
Optimización adicional: para el caso de superposición parcial, tenemos que ejecutar un bucle para calcular el recuento de los mismos números en ambos lados. Para evitar este ciclo y realizar esta operación en O(1), podemos almacenar el índice de la primera aparición de cada número en la array dada y, por lo tanto, al realizar algunos cálculos previos, podemos encontrar el conteo requerido en O(1).
Complejidad de tiempo:
La complejidad de tiempo para la construcción del árbol es O(n). La complejidad del tiempo para consultar es O (Log n).
Tema relacionado: Árbol de segmentos
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA