Clasificación de elementos de array por frecuencia | Conjunto 3 (usando STL)

Dada una array de enteros, ordene la array según la frecuencia de los elementos. Si las frecuencias de dos elementos son iguales, imprímelas en orden creciente. Ejemplos:

Input : arr[] = {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}
Output : 3 3 3 3 2 2 2 12 12 4 5
Explanation :
No. Freq
2  : 3
3  : 4
4  : 1
5  : 1
12 : 2

Hemos discutido diferentes enfoques en las siguientes publicaciones: Ordenar elementos por frecuencia | Set 1 Ordenar elementos por frecuencia | Conjunto 2 Podemos resolver este problema usando mapa y pares . Inicialmente creamos un mapa tal que map[element] = freq. Una vez que terminamos de construir el mapa, creamos una array de pares. Se utilizará un par que almacene elementos y su frecuencia correspondiente para fines de clasificación. Escribimos una función de comparación personalizada que compara dos pares primero en función de la frecuencia y si hay un empate en función de los valores. 

A continuación se muestra su implementación en C++: 

CPP

// C++ program to sort elements by frequency using
// STL
#include <bits/stdc++.h>
using namespace std;
 
// function to compare two pairs for inbuilt sort
bool compare(pair<int,int> &p1,
            pair<int, int> &p2)
{
    // If frequencies are same, compare
    // values
    if (p1.second == p2.second)
        return p1.first < p2.first;
    return p1.second > p2.second;
}
 
// function to print elements sorted by freq
void printSorted(int arr[], int n)
{
    // Store items and their frequencies
    map<int, int> m;
    for (int i = 0; i < n; i++)
        m[arr[i]]++;
 
    // no of distinct values in the array
    // is equal to size of map.
    int s = m.size();
 
    // an array of pairs
    pair<int, int> p[s];
 
    // Fill (val, freq) pairs in an array
    // of pairs.
    int i = 0;
    for (auto it = m.begin(); it != m.end(); ++it)
        p[i++] = make_pair(it->first, it->second);
 
    // sort the array of pairs using above
    // compare function.
    sort(p, p + s, compare);
 
    cout << "Elements sorted by frequency are: ";
    for (int i = 0; i < s; i++)
    {
        int freq = p[i].second;
        while (freq--)
            cout << p[i].first << " ";
    }
}
 
// driver program
int main()
{
    int arr[] = {2, 3, 2, 4, 5, 12, 2, 3,
                3, 3, 12};
    int n = sizeof(arr)/ sizeof(arr[0]);
    printSorted(arr, n);
    return 0;
}
Producción

Elements sorted by frequency are: 3 3 3 3 2 2 2 12 12 4 5 

Complejidad de tiempo: O (n Log n) 

Este artículo es una contribución de Aditi Sharma . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *