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; }
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