难题妙解——前K个高频单词

1.题目解析

692.前K个高频单词

本题⽬我们利⽤map统计出次数以后，返回的答案应该按单词出现频率由⾼到低排序，有⼀个特殊要 求，如果不同的单词有相同出现频率，按字典顺序排序 

2.算法原理

2.1思路一

⽤排序找前k个单词，因为map中已经对key单词排序过，也就意味着遍历map时，次数相同的单词， 字典序⼩的在前⾯，字典序⼤的在后⾯。那么我们将数据放到vector中⽤⼀个稳定的排序就可以实现上⾯特殊要求，但是sort底层是快排，是不稳定的，所以我们要⽤stable_sort，他是稳定的

class Solution {
public:struct Compare{bool operator()(const pair<string, int>& x, const pair<string, int>& y)const{return x.second > y.second;}};vector<string> topKFrequent(vector<string>& words, int k) {map<string, int> countMap;for(auto& e : words){countMap[e]++;}vector<pair<string, int>> v(countMap.begin(), countMap.end());// 仿函数控制降序 stable_sort(v.begin(), v.end(), Compare());//sort(v.begin(), v.end(), Compare());// 取前k个 vector<string> strV;for(int i = 0; i < k; ++i){strV.push_back(v[i].first);}return strV;}
};

2.2思路二

将map统计出的次数的数据放到vector中排序，或者放到priority_queue中来选出前k个。利⽤仿函数 强⾏控制次数相等的，字典序⼩的在前⾯ 

class Solution {
public:struct Compare{bool operator()(const pair<string, int>& x, const pair<string, int>& y)const{return x.second > y.second || (x.second == y.second && x.first < 
y.first);;}};vector<string> topKFrequent(vector<string>& words, int k) {map<string, int> countMap;for(auto& e : words){countMap[e]++;}vector<pair<string, int>> v(countMap.begin(), countMap.end());// 仿函数控制降序,仿函数控制次数相等，字典序⼩的在前⾯ sort(v.begin(), v.end(), Compare());// 取前k个 vector<string> strV;for(int i = 0; i < k; ++i){strV.push_back(v[i].first);}return strV;}
};class Solution {
public:struct Compare{bool operator()(const pair<string, int>& x, const pair<string, int>& y)const{// 要注意优先级队列底层是反的，⼤堆要实现⼩于⽐较，所以这⾥次数相等，想要字典
序⼩的在前⾯要⽐较字典序⼤的为真 return x.second < y.second || (x.second == y.second && x.first > 
y.first);}};vector<string> topKFrequent(vector<string>& words, int k) {map<string, int> countMap;for(auto& e : words){countMap[e]++;}// 将map中的<单词，次数>放到priority_queue中，仿函数控制⼤堆，次数相同按照字典
序规则排序 priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> 
p(countMap.begin(), countMap.end());vector<string> strV;for(int i = 0; i < k; ++i){strV.push_back(p.top().first);p.pop();}return strV;}
};