LeetCode 451

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

示例 1:

输入:
"tree"

输出:
"eert"

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

示例 2:

输入:
"cccaaa"

输出:
"cccaaa"

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

示例 3:

输入:
"Aabb"

输出:
"bbAa"

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

思路：先创建一个哈希表用来映射字符串中的单个字符的出现次数与该字符相对应，再创建一个multimap来把这个哈希表以表中每一对键值的出现次数为准，升序装入，最后在女遍历这个哈希表，因为题目要求即使是重复字符结果也要显示出来，所以就得每次遍历判断该字符的出现次数，然后使用一个while循环来输出重复字符。
堆这一块就暂时结束，基本的解题方法就是这几种

源代码如下：

class Solution {
public:
    string frequencySort(string s) {
        map<char, int> count;
        multimap<int, char> chmap;
        for (char ch : s) {
            count[ch]++;
        }
        for (auto f = count.begin(); f != count.end(); f++) {
            chmap.insert(make_pair(f->second, f->first));
        }
        string str;
        int idx = s.size()-1;
        for (auto it = chmap.begin(); it != chmap.end(); it++) {
            int fr = it->first;
            char x = it->second;
            while (fr-- > 0) {
            s[idx--] = x;
            }
        }
        return s;
    }
};