692. 前K个高频单词

题目来源：力扣

题目描述：

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例 1：

输入: words = ["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:struct Greater{bool operator()(const pair<string,int>& kv1, const pair<string,int>& kv2){return kv1.second > kv2.second;}};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> countMap;for(const auto& e : words){countMap[e]++;}vector<pair<string,int>> KvVec(countMap.begin(),countMap.end());stable_sort(KvVec.begin(),KvVec.end(),Greater());//和sort一样，但是stable_sort是稳定的排序vector<string> ret;for(int i=0;i<k;i++){ret.push_back(KvVec[i].first);}return ret;}
};

class Solution {
public:struct Greater{bool operator()(const pair<string,int>& kv1, const pair<string,int>& kv2){return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first);//频率大的在前面，频率相等的情况下，就去比较字典序，小的在前面}};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> countMap;for(const auto& e : words){countMap[e]++;}vector<pair<string,int>> KvVec(countMap.begin(),countMap.end());sort(KvVec.begin(),KvVec.end(),Greater());vector<string> ret;for(int i=0;i<k;i++){ret.push_back(KvVec[i].first);}return ret;}
};

这里有两种方法，一种是正常使用sort，一种是不使用sort

class Solution {
public:vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> countMap;for(const auto& e : words){countMap[e]++;}multimap<int,string,greater<int>> sortMap;//这里依赖map底层实现，有些平台可能过不了for(auto& kv : countMap){sortMap.insert(make_pair(kv.second,kv.first));}vector<string> v;auto it = sortMap.begin();while(k--){v.push_back(it->second);++it;}return v;}
};

思路：
 这道题麻烦的是按照字典序去排列，sort是对随机迭代器进行排序的，而map是双向迭代器，也就是说map是无法使用sort的，所以我们在上边倒来倒去的倒数据，这道题就是用map统计一下频率然后按频率排序即可，这里需要给sort设计一个仿函数，让频率大的在前面，如果使用原始的sort，那么会面临因为sort是不稳定的排序，所以要自己加一些条件，或者换一个稳定的排序函数，比如stable_sort，接着我们把前k个放在一个vector里返回即可

除了sort可以排序，map也可以再排序，我们反过来再搞一个multimap（map会去重）排序即可，这里需要给map传第三个模板参数，这里依赖底层实现，有的平台可能不会通过，接着一样再把前k个放入vector返回即可