一、题目

二、思路

（1）根据词频排序，很容易想到用哈希表统计每个字符的个数，然后排序。对于“求前k个”或“排序”的题目可以使用堆排序，用优先级队列实现最大堆，进行堆排序，堆顶即当前的最大值。因为我们的pair<char, int>的second才是对应字符（first）的词频，需要的是对second进行排序，所以重写cmp。

（2）string(num, c)是生成一个包含num个c字符的字符串，这题试了用for循环实现竟然会超时。

（3）其实vector就能够排序了，不用priority_queue也是可以的。

【C++中STL的优先级队列】
在C++的stl中有priority_queue优先级队列，其具体参数如下：
priority_queue<Type, Container, Functional>：

• Type 就是数据类型，
• Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector）
• Functional 就是比较的方式。

PS：当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆。

cmp：大的优先级在前面，注意：堆的优先级的返回值与排序的正好相反。

三、代码

class Solution {
struct cmp{
    bool operator()(pair<char, int>&a, pair<char, int>&b){
        return a.second < b.second;
        //大的优先级在前面，注意：堆的优先级的返回值与排序的正好相反
    }
};
public:
    using stu = pair<char, int>; 
    string frequencySort(string s) {
        unordered_map<char, int>mp(26);
        for(int i = 0; i < s.size(); i++){
            mp[s[i]]++;
        }
        priority_queue<stu, vector<stu>, cmp>pq;
        for(auto &[key, value]: mp){
            //每一个pair
            pq.push({key, value});
        }
        string ans = "";
        while(!pq.empty()){
            auto [c, num] = pq.top();
            pq.pop();
            ans = ans + string(num, c);
        }
        return ans;
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/122610215