Ordenar elementos por frecuencia | Conjunto 4 (Enfoque eficiente usando hash)

Imprime los elementos de una array en frecuencia decreciente si 2 números tienen la misma frecuencia y luego imprime el que vino primero.

Ejemplos: 

Input : arr[] = {2, 5, 2, 8, 5, 6, 8, 8}
Output : arr[] = {8, 8, 8, 2, 2, 5, 5, 6}

Input : arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
Output : arr[] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
 

Hemos discutido diferentes enfoques en las siguientes publicaciones: 
Ordenar elementos por frecuencia | Set 1  
Ordenar elementos por frecuencia | Set 2  
Clasificación de elementos de array por frecuencia | Conjunto 3 (usando STL)
Todos los enfoques anteriores funcionan en tiempo O (n Log n), donde n es el número total de elementos. En esta publicación, se analiza un nuevo enfoque que funciona en tiempo O (n + m Log m) , donde n es el número total de elementos y m es el número total de elementos distintos.

La idea es usar hash . 

1. Insertamos todos los elementos y sus conteos en un hash. Este paso toma O(n) tiempo donde n es el número de elementos.
2. Copiamos el contenido del hash en una array (o vector) y los ordenamos por conteo. Este paso toma el tiempo O(m Log m) donde m es el número total de elementos distintos.
3. Para mantener el orden de los elementos si la frecuencia es la misma, usamos otro hash que tiene la clave como elementos de la array y el valor como índice. Si la frecuencia es la misma para dos elementos, ordene los elementos según el índice.

La siguiente imagen es una ejecución en seco del enfoque anterior:

No necesitamos declarar otro mapa m2, ya que no proporciona el resultado esperado adecuado para el problema.

en cambio, solo necesitamos verificar los primeros valores de los pares enviados como parámetros en la función sortByVal.

A continuación se muestra la implementación del enfoque anterior:

//     CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Used for sorting by frequency. And if frequency is same,
// then by appearance
bool sortByVal(const pair<int, int>& a,
                      const pair<int, int>& b)
{
 
   // If frequency is same then sort by index
   if (a.second == b.second) 
       return a.first < b.first;
 
   return a.second > b.second;
}
 
// function to sort elements by frequency
vector<int>sortByFreq(int a[], int n)
{
 
   vector<int>res;
 
   unordered_map<int, int> m;
 
   vector<pair<int, int> > v;
 
   for (int i = 0; i < n; ++i) {
 
       // Map m is used to keep track of count 
       // of elements in array
       m[a[i]]++;     
   }
 
   // Copy map to vector
   copy(m.begin(), m.end(), back_inserter(v));
 
   // Sort the element of array by frequency
   sort(v.begin(), v.end(), sortByVal);
 
   for (int i = 0; i < v.size(); ++i) 
      while(v[i].second--)
      {
              res.push_back(v[i].first);
      }
 
   return res;
}
 
// Driver program
int main()
{
 
   int a[] = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 };
   int n = sizeof(a) / sizeof(a[0]);
   vector<int>res;
   res = sortByFreq(a, n);
 
   for(int i = 0;i < res.size(); i++)
         cout<<res[i]<<" ";
 
   return 0;
 
}

# Used for sorting by frequency. And if frequency is same,
# then by appearance
from functools import cmp_to_key
 
def sortByVal(a,b):
 
    # If frequency is same then sort by index
    if (a[1] == b[1]):
        return a[0] - b[0]
 
    return b[1] - a[1]
 
# function to sort elements by frequency
def sortByFreq(a, n):
    res = []
    m = {}
    v = []
 
    for i in range(n):
 
        # Map m is used to keep track of count
        # of elements in array
        if(a[i] in m):
            m[a[i]] = m[a[i]]+1
        else:
            m[a[i]] = 1
 
    for key,value in m.items():
        v.append([key,value])
 
    # Sort the element of array by frequency
    v.sort(key = cmp_to_key(sortByVal))
 
    for i in range(len(v)):
        while(v[i][1]):
            res.append(v[i][0])
            v[i][1] -= 1
 
    return res
 
 
# Driver program
 
a = [ 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 ]
n = len(a)
res = []
res = sortByFreq(a, n)
 
for i in range(len(res)):
    print(res[i],end = " ")
 
 
# This code is contributed by shinjanpatra

<script>
 
//     JavaScript program for the above approach
 
 
// Used for sorting by frequency. And if frequency is same,
// then by appearance
function sortByVal(a,b)
{
 
// If frequency is same then sort by index
if (a[1] == b[1])
    return a[0] - b[0];
 
return b[1] - a[1];
}
 
// function to sort elements by frequency
function sortByFreq(a, n)
{
 
let res = [];
 
let m = new Map();
 
let v = [];
 
for (let i = 0; i < n; ++i) {
 
    // Map m is used to keep track of count
    // of elements in array
    if(m.has(a[i]))
        m.set(a[i],m.get(a[i])+1);
    else
        m.set(a[i],1);
}
 
for(let [key,value] of m){
    v.push([key,value]);
}
 
// Sort the element of array by frequency
v.sort(sortByVal)
 
for (let i = 0; i < v.length; ++i)
    while(v[i][1]--)
    {
        res.push(v[i][0]);
    }
 
    return res;
}
 
// Driver program
 
let a = [ 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 ];
let n = a.length;
let res = [];
res = sortByFreq(a, n);
 
for(let i = 0;i < res.length; i++)
    document.write(res[i]," ");
 
 
// This code is contributed by shinjanpatra
 
</script>

8 8 8 2 2 5 5 -1 6 9999999 

Complejidad de tiempo: O(n) + O(m Log m) donde n es el número total de elementos y m es el número total de elementos distintos
Espacio auxiliar: O(n)

Este artículo es una contribución de Aarti_Rathi y Ankur Singh y mejorado por Ankur Goel . 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.