根据字符出现频率排序

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

题目链接

示例:

输入:
"tree"

输出:
"eert"

解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

思路

解法一：

  1. 使用 map 存储元素及其出现次数；
  2. 定义一个堆，并自定义比较方法；
  3. 将 map 中的元素都放入堆中；
  4. 遍历堆中元素拼接字符串。
class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> m;
        for (auto & c : s) {
            m[c]++;
        }
        auto cmp = [](pair<char, int> &a, pair<char, int> &b)
        {
            return a.second <= b.second;
        };

        priority_queue<pair<char, int>, vector<pair<char, int>>, decltype(cmp)> heap(cmp);

        for (auto &i : m) {
            heap.push(i);
        }
        string res;

        while (!heap.empty()) {
            res += string(heap.top().second, heap.top().first);
            heap.pop();
        }
        return res;
    }
};