算法：按频率对元素排序|S4（使用哈希的有效方法）

如果2个数字具有相同的频率, 则以递减的频率打印数组的元素, 然后打印第一个出现的频率。

例子：

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}

我们在以下帖子中讨论了不同的方法：

按频率对元素排序|S1

按频率对元素排序|S2

按频率对数组元素排序S3(使用STL)

以上所有方法都在O(n Log n)时间内有效，其中n是元素总数。在这篇文章中，我们讨论了一种在O(n + m Log m)时间下工作的新方法，其中n是元素的总数，m是不同元素的总数。

这里的方法是使用哈希

1. 我们将所有元素及其计数插入哈希中。此步骤花费O(n)时间, 其中n是元素数。
2. 我们将哈希的内容复制到数组(或向量)中, 并按计数对其进行排序。此步骤花费O(m Log m)时间, 其中m是不同元素的总数。
3. 为了保持频率相同时元素的顺序, 我们使用另一个散列, 该散列的键为数组的元素, 而值为索引。如果两个元素的频率相同, 则根据索引对元素进行排序。

下图是上述方法的模拟：

我们不需要声明另一个映射m2, 因为它没有为问题提供适当的预期结果。

相反, 我们只需要检查sortByVal函数中作为参数发送的对的第一个值即可。

下面是上述方法的实现：

C ++

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

输出如下：

8 8 8 2 2 5 5 6 -1 9999999