Given a string, sort it in decreasing order based on the frequency of characters.
Example 1:
Input:
"tree"Output:
"eert"本题就是要把字符串里的数字按频率降序输出。注意题目中说，频率相同的字母顺序随便排都是合理答案。
一看次数，直接想到哈希表，所以我用了map，发现其实好多map不知道的基础知识，有时间了在补一补吧。先说思路
map建立字符和出现次数的关系，map<char,int>.然后在根据value对map进行降序排列就可以了。难点就是如何降序排列。
可以先看一下这篇博客https://blog.csdn.net/qq_26399665/article/details/52969352。基本思想就是将map放进vector中，在对vector进行排序。
排完之后直接输出就可以，但是注意的是，输出的时候遇到每个字符多次的要输出多次该字符，就是在要嵌套一层循环，否则就只会输出一个该字符。
AC代码：
class Solution {
public:static bool cmp(const pair<char,int> &p1,const pair<char,int> &p2) {return p1.second>p2.second;}string frequencySort(string s) {map<char,int> m;for(int i=0;i<s.length();i++){m[s[i]]++;}vector<pair<char,int>> arr;for (map<char,int>::iterator it=m.begin();it!=m.end();++it){arr.push_back(make_pair(it->first,it->second));}sort(arr.begin(),arr.end(),cmp);int i=0;for(vector<pair<char,int>>::iterator it=arr.begin();it!=arr.end();++it){for(int j=0;j<it->second;j++){s[i++]=it->first; }}return s;}
};今天看了另一个方法，思路一样，但是代码很简单，用了自动排序的数据结构priority_queue ，优先队列。
定义了priority_queue<pair<int,int>>,优先队列会自动排序，默认是降序，优先级大的在前，符合这道题的要求。如果数据类型是pair的话，则会按pair 的first元素排序，first相同在按second排序。
所以生成pair的时候将频率当first元素。
AC代码：
class Solution {
public:string frequencySort(string s) {string res = "";priority_queue<pair<int, char>> q;unordered_map<char, int> m;for (char c : s) ++m[c];for (auto a : m) q.push({a.second, a.first});while (!q.empty()) {auto t = q.top(); q.pop();res.append(t.first, t.second);}return res;}
};