前K个高频单词（map+multimap）1
需积分: 0 142 浏览量
2022-08-03
13:48:51
上传
评论
收藏 515KB PDF 举报
前 K 个高频单词
给一非空的单词列表，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序
排序。
示例 1：
输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为 2 次。
注意，按字母顺序 "i" 在 "love" 之前。
示例 2：
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is",
"is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
//1,建立 map 映射关系，通过 key-vaule 统计所有单词出现的次数记录为 value
// map 记录后，内部顺序按照每个单词字母顺序进行排序
//2，建立 multimap，映射关系翻转，以频次作为 key 值进行插入
// multimap 记录后，内部顺序按照单词出现频次顺序进行排序
map<string,int> mp;
for(auto& wd:words)
{
mp[wd]++;//在 mp 中，按字母顺序排序
}
multimap<int,string,greater<int>> mmp;
for(auto& p:mp)
{
mmp.insert(make_pair(p.second,p.first));//以单词出现频次作为 key
插入，按照频次由高到低排序
评论0