Dada una array arr[] de tamaño N , la tarea es encontrar la frecuencia de cada elemento distinto presente en la array dada.
Ejemplos:
Entrada: arr[] = { 1, 100000000, 3, 100000000, 3 }
Salida: { 1 : 1, 3 : 2, 100000000 : 2 }
Explicación:
Los distintos elementos de la array dada son { 1, 100000000, 3 }
Frecuencia de 1 en la array dada es 1.
La frecuencia de 100000000 en la array dada es 2.
La frecuencia de 3 en la array dada es 2.
Por lo tanto, la salida requerida es { 1 : 1, 100000000 : 2, 3 : 2 }Entrada: arr[] = { 100000000, 100000000, 800000000, 100000000 }
Salida: { 100000000 : 3, 800000000 : 1}
Enfoque: El problema se puede resolver utilizando la técnica de búsqueda binaria . Siga los pasos a continuación para resolver el problema:
- Ordene la array en orden ascendente .
- Recorra la array y, para cada elemento distinto de la array, encuentre su índice de límite inferior y sus índices de límite superior mediante la búsqueda binaria y almacene en variables, por ejemplo, LB y UB , respectivamente. Imprime el valor de (UB – LB) como la frecuencia de ese elemento.
A continuación se muestra la implementación del enfoque anterior:
C
// C program to implement
// the above approach
#include <stdio.h>
#include <stdlib.h>
// Comparator function to sort
// the array in ascending order
int cmp(const void* a,
const void* b)
{
return (*(int*)a - *(int*)b);
}
// Function to find the lower_bound of X
int lower_bound(int arr[], int N, int X)
{
// Stores minimum possible
// value of the lower_bound
int low = 0;
// Stores maximum possible
// value of the lower_bound
int high = N;
// Calculate the upper_bound
// of X using binary search
while (low < high) {
// Stores mid element
// of low and high
int mid = low + (high - low) / 2;
// If X is less than
// or equal to arr[mid]
if (X <= arr[mid]) {
// Find lower_bound in
// the left subarray
high = mid;
}
else {
// Find lower_bound in
// the right subarray
low = mid + 1;
}
}
// Return the lower_bound index
return low;
}
// Function to find the upper_bound of X
int upper_bound(int arr[], int N, int X)
{
// Stores minimum possible
// value of the upper_bound
int low = 0;
// Stores maximum possible
// value of the upper_bound
int high = N;
// Calculate the upper_bound
// of X using binary search
while (low < high) {
// Stores mid element
// of low and high
int mid = low + (high - low) / 2;
// If X is greater than
// or equal to arr[mid]
if (X >= arr[mid]) {
// Find upper_bound in
// right subarray
low = mid + 1;
}
// If X is less than arr[mid]
else {
// Find upper_bound in
// left subarray
high = mid;
}
}
// Return the upper_bound index
return low;
}
// Function to find the frequency
// of an element in the array
int findFreq(int arr[], int N,
int X)
{
// Stores upper_bound index of X
int UB = upper_bound(arr, N, X);
// Stores lower_bound index of X
int LB = lower_bound(arr, N, X);
return (UB - LB);
}
// Utility function to print the frequency
// of each distinct element of the array
void UtilFindFreqArr(int arr[], int N)
{
// Sort the array in
// ascending order
qsort(arr, N,
sizeof(int), cmp);
// Print start bracket
printf("{ ");
// Traverse the array
for (int i = 0; i < N;) {
// Stores frequency
// of arr[i];
int fr = findFreq(arr, N,
arr[i]);
// Print frequency of arr[i]
printf("%d : %d",
arr[i], fr);
// Update i
i++;
// Remove duplicate elements
// from the array
while (i < N && arr[i] == arr[i - 1]) {
// Update i
i++;
}
// If arr[i] is not
// the last array element
if (i <= N - 1) {
printf(", ");
}
}
// Print end bracket
printf(" }");
}
// Driver Code
int main()
{
int arr[] = { 1, 100000000, 3,
100000000, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
UtilFindFreqArr(arr, N);
}
{ 1 : 1, 3 : 2, 100000000 : 2 }
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(1)