题目描述

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

样例

输入：
"tree"

输出：
"eert"

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

输入：
"cccaaa"

输出：
"cccaaa"

解释：
'c' 和 'a' 都出现三次。此外，"aaaccc" 也是有效的答案。
注意 "cacaca" 是不正确的，因为相同的字母必须放在一起。

输入：
"Aabb"

输出：
"bbAa"

解释：
此外，"bbaA" 也是一个有效的答案，但 "Aabb" 是不正确的。
注意 'A' 和 'a' 被认为是两种不同的字符。

算法

(哈希表 + 排序) $O(L \log L)$

1. 用 unordered_map 统计每个字符的出现次数。
2. 将每个字符的出现次数和字符本身构成 pair，加入到数组中。
3. 对数组排序，然后从大到小组合为答案即可。

时间复杂度

• 最坏情况下，需要对长度为 $L$ 的 pair 数组进行排序，故总时间复杂度为 $O(L \log L)$，其中 $L$ 为字符串的长度。

空间复杂度

• 需要 $O(L)$ 的额外空间存储中间结果和答案。

C++ 代码

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> hash;
        for (auto &c : s)
            hash[c]++;

        vector<pair<int, char>> chs;
        unordered_map<char, int>::iterator it;
        for (it = hash.begin(); it != hash.end(); it++)
            chs.push_back(make_pair(it -> second, it -> first));

        sort(chs.begin(), chs.end());
        reverse(chs.begin(), chs.end());

        string ans = "";
        for (auto &ch : chs)
            ans += string(ch.first, ch.second);

        return ans;
    }
};