Dada una array de enteros, ordene la array según la frecuencia de los elementos. Por ejemplo, si la array de entrada es {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}, modifique la array a {3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5}.
En la publicación anterior , hemos discutido todos los métodos para ordenar según la frecuencia. En esta publicación, el método 2 se analiza en detalle y se proporciona la implementación de C++ para el mismo.
A continuación se detalla el algoritmo.
- Cree un BST y mientras crea BST mantenga el recuento, es decir, la frecuencia de cada elemento entrante en el mismo BST. Este paso puede tardar un tiempo O(nLogn) si se utiliza un BST autoequilibrado.
- Realice un recorrido en orden de BST y almacene cada elemento y el recuento de cada elemento en una array auxiliar. Llamemos a la array auxiliar como ‘contar[]’. Tenga en cuenta que cada elemento de esta array es un elemento y un par de frecuencias. Este paso toma tiempo O(n).
- Ordene ‘count[]’ según la frecuencia de los elementos. Este paso toma el tiempo O(nLohn) si se usa un algoritmo de clasificación O(nLogn).
- Recorra la array ordenada ‘count[]’. Para cada elemento x, imprímalo ‘freq’ veces donde ‘freq’ es la frecuencia de x. Este paso toma tiempo O(n).
La complejidad de tiempo general del algoritmo puede ser mínima O (nLogn) si usamos un algoritmo de clasificación O (nLogn) y usamos un BST autoequilibrado con operación de inserción O (Logn) .
A continuación se muestra la implementación del algoritmo anterior.
C++
// Implementation of above algorithm in C++.
#include <iostream>
#include <stdlib.h>
using namespace std;
/* A BST node has data, freq, left and right pointers */
struct BSTNode
{
struct BSTNode *left;
int data;
int freq;
struct BSTNode *right;
};
// A structure to store data and its frequency
struct dataFreq
{
int data;
int freq;
};
/* Function for qsort() implementation. Compare frequencies to
sort the array according to decreasing order of frequency */
int compare(const void *a, const void *b)
{
return ( (*(const dataFreq*)b).freq - (*(const dataFreq*)a).freq );
}
/* Helper function that allocates a new node with the given data,
frequency as 1 and NULL left and right pointers.*/
BSTNode* newNode(int data)
{
struct BSTNode* node = new BSTNode;
node->data = data;
node->left = NULL;
node->right = NULL;
node->freq = 1;
return (node);
}
// A utility function to insert a given key to BST. If element
// is already present, then increases frequency
BSTNode *insert(BSTNode *root, int data)
{
if (root == NULL)
return newNode(data);
if (data == root->data) // If already present
root->freq += 1;
else if (data < root->data)
root->left = insert(root->left, data);
else
root->right = insert(root->right, data);
return root;
}
// Function to copy elements and their frequencies to count[].
void store(BSTNode *root, dataFreq count[], int *index)
{
// Base Case
if (root == NULL) return;
// Recur for left subtree
store(root->left, count, index);
// Store item from root and increment index
count[(*index)].freq = root->freq;
count[(*index)].data = root->data;
(*index)++;
// Recur for right subtree
store(root->right, count, index);
}
// The main function that takes an input array as an argument
// and sorts the array items according to frequency
void sortByFrequency(int arr[], int n)
{
// Create an empty BST and insert all array items in BST
struct BSTNode *root = NULL;
for (int i = 0; i < n; ++i)
root = insert(root, arr[i]);
// Create an auxiliary array 'count[]' to store data and
// frequency pairs. The maximum size of this array would
// be n when all elements are different
dataFreq count[n];
int index = 0;
store(root, count, &index);
// Sort the count[] array according to frequency (or count)
qsort(count, index, sizeof(count[0]), compare);
// Finally, traverse the sorted count[] array and copy the
// i'th item 'freq' times to original array 'arr[]'
int j = 0;
for (int i = 0; i < index; i++)
{
for (int freq = count[i].freq; freq > 0; freq--)
arr[j++] = count[i].data;
}
}
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
/* Driver program to test above functions */
int main()
{
int arr[] = {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12};
int n = sizeof(arr)/sizeof(arr[0]);
sortByFrequency(arr, n);
printArray(arr, n);
return 0;
}
Salida :
3 3 3 3 2 2 2 12 12 5 4
Ejercicio: la implementación anterior no garantiza el orden original de los elementos con la misma frecuencia (por ejemplo, 4 viene antes que 5 en la entrada, pero 4 viene después del 5 en la salida). Ampliar la implementación para mantener el orden original. Por ejemplo, si dos elementos tienen la misma frecuencia, imprima el primero en la array de entrada.
Este artículo ha sido compilado por Chandra Prakash . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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