Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string. Return the sorted string. If there are multiple answers, return any of them.
考察了map的创建，map转存到vector，函数参数传递进去自定义排序（关系仿函数）这题还是比较需要基本功的。
class Solution {
public:
// 仿函数
typedef pair<char,int> PAIR;
struct CmpByValue{
bool operator()(const PAIR& lhs,const PAIR& rhs){
return lhs.second>=rhs.second;//
}
};
string frequencySort(string s) {
//按照频率统计字符串 第一件事情就是要提取出字符 计算频率
//哈希表进行排序？
// 处理步骤 先用map村数值 然后转存到vector 指定仿函数修改排序规则
map<char,int> dp;
for(char ss:s){
if(dp.find(ss)==dp.end()){
dp[ss]=1;
}
else{
dp[ss]++;
}
}
// 将map元素转存到vector中
vector<PAIR> dp2(dp.begin(),dp.end());
// 对vector排序
sort(dp2.begin(),dp2.end(),CmpByValue());
//根据排序后的元素拼接新的字符串
string res="";
for(auto dd:dp2){
string tmp(dd.second,dd.first);
res+=tmp;
}
return res;
}
};
为了避免map中key键值重复的问题 利用优先队列（默认大顶堆）重建以出现次数为key的优先队列，减少时间复杂度。
class Solution {
public:
string frequencySort(string s) {
//按照频率统计字符串 第一件事情就是要提取出字符 计算频率
//哈希表进行排序？
// 处理步骤 先用map村数值 然后转存到vector 指定仿函数修改排序规则
map<char,int> dp;
for(char ss:s){
dp[ss]++;
}
//利用优先队列 大顶堆直接做
priority_queue<pair<int,char>> q;//这样避免了key不能重复的问题
string res="";
for(auto dd:dp){
q.push({dd.second,dd.first});
}
while(!q.empty()){
auto c=q.top();
string tmp(c.first,c.second);
res+=tmp;
q.pop();
}
return res;
}
};