题目
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。。
示例1：
输入："tree"
输出："eert"
解释：'e'出现两次，'r'和't'都只出现一次。因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
示例2：
输入："cccaaa"
输出："cccaaa"
解释：'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例3：
输入："Aabb"
输出："bbAa"
解释：此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。注意'A'和'a'被认为是两种不同的字符。
思路
提到统计出现频率，就使用map；接着是按次数排序，即按map的value进行排序，因此使用最大堆将map中的元素压入，堆顶就是出现频率最高的元素；最后遍历堆，根据value值控制输出次数。
解答
class Solution {
public:
typedef pair<char, int> mypair;
struct cmp{ //最大堆
bool operator()(const mypair &left, const mypair &right) const {
return left.second < right.second;
}
};
public:
string frequencySort(string s) {
if(s.size() < 2) return s;
string ans;
mypair temp;
priority_queue<mypair, vector<mypair>, cmp> que; //最大堆
unordered_map<char, int> hash;
for(auto c : s) hash[c]++; //统计频率
for(auto iter : hash) que.push(iter); //入堆
while(!que.empty()){
temp = que.top();
//出现几次就push几次
for(int i=0; i < temp.second; i++)
ans.push_back(temp.first);
que.pop();
}
return ans;
}
};
【关注公众号DoCode，每日一道LeetCode，将零碎时间利用起来】
