按频率对元素进行排序（C++ 中的 Map 与 Bucket 方法）

Source: Dev.to

Problem Idea

给定一个数组，按出现频率降序排序元素，并重新构建数组，使出现频率最高的元素首先出现。

Example
Input: [1,1,2,2,2,3]
Output: [2,2,2,1,1,3]

Approach 1: unordered_map + Sorting

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1,1,2,2,2,3};
    unordered_map<int,int> freq;
    vector<int> res;

    for (int x : v) freq[x]++;

    vector<pair<int,int>> vec(freq.begin(), freq.end());

    sort(vec.begin(), vec.end(),
         [](auto &a, auto &b){ return a.second > b.second; });

    for (auto &p : vec) {
        for (int i = 0; i 

Time & Space Complexity

• Frequency count: O(n) → 频率计数：O(n)
• Sorting: O(m log m) where m is the number of distinct elements → 排序：O(m log m)，其中 m 为不同元素的数量
• Reconstruction: O(n) → 重建：O(n)

Total time: O(n + m log m)
Space: O(m) for the map and vector of pairs. → 空间：O(m)（用于映射和键值对向量）

Approach 2: Bucket (Counting Sort)

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1,1,2,2,2,3};

    const int MAX = 100;               // maximum possible value (adjust as needed)
    vector<int> freq(MAX, 0);

    for (int x : v) freq[x]++;

    int maxFreq = 0;
    for (int f : freq) maxFreq = max(maxFreq, f);

    vector<vector<int>> bucket(maxFreq + 1);
    for (int i = 0; i < (int)freq.size(); ++i) {
        if (freq[i] > 0)
            bucket[freq[i]].push_back(i);
    }

    vector<int> res;
    for (int f = maxFreq; f > 0; f--) {
        for (int val : bucket[f]) {
            for (int i = 0; i < f; i++)
                res.push_back(val);
        }
    }

    for (int x : res) cout << x << " ";
}

Time & Space Complexity

• Frequency count: O(n) → 频率计数：O(n)
• Bucket traversal & reconstruction: O(n) → 桶遍历与重建：O(n)

Total time: O(n)

• Frequency array: O(k) → 频率数组：O(k)
• Buckets: O(k) → 桶：O(k)
• Result vector: O(n) → 结果向量：O(n)

Total space: O(n + k) → 总空间：O(n + k)

What I Learned

• Sorting is not always required; bucket storage can replace sorting with simple indexing. → 排序并非总是必要的；使用桶存储可以通过简单的索引替代排序。
• Constant factors are ignored in Big‑O notation (O(2k) → O(k)). → 在大 O 表示法中会忽略常数因子（O(2k) → O(k)）。
• unordered_map is flexible, but a fixed‑size frequency array is faster when the value range is known. → unordered_map 灵活，但当值范围已知时，固定大小的频率数组更快。

Practice Challenge

• Solve the problem again using only unordered_map without sorting. → 仅使用 unordered_map 且不 进行排序，重新解决该问题。
• Adapt the bucket idea to work with an unordered_map‑based frequency table. → 将桶的思路改造成适用于基于 unordered_map 的频率表。