Leetcode 451

题目要求

给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。

核心算法和原理

• 哈希表装每个字符的出现次数，转换为vector<pair<char, int>> 后根据second降序排序

• 直接对字符串进行排序的话会很慢，不知原因

• （重点是这种map → vector<pair<>>的写法）

代码

class Solution {
public:
    unordered_map<char, int> m;

    static bool cmp(pair<char, int>& a, pair<char, int>& b) {
        return a.second > b.second;
    }
    string frequencySort(string s) {
        for (char c : s) {
            m[c]++;
        }

        vector<pair<char, int>> pairm(m.begin(), m.end());
        ranges::sort(pairm, cmp);
        int i = 0;
        for (auto& p: pairm) {
            int cnt = p.second;
            while (cnt--) {
                s[i++] = p.first;
            }
        }
        return s;
    }
};