一、題目鏈接

692.前K個高頻單詞

二、題目

三、分析

本題目我們利用map統計出次數以后，返回的答案應該按單詞出現頻率由高到低排序，有一個特殊要求，如果不同的單詞有相同出現頻率，按字典順序排序。

解法一：用排序找前k個單詞，因為map中已經對key單詞排序過，也就意味著遍歷map時，次數相同的單詞，字典序小的在前面，字典序大的在后面。那么我們將數據放到vector中用一個穩定的排序就可以實現上面特殊要求，但是sort底層是快排，是不穩定的，所以我們要用stable_sort，他是穩定的。

涉及到排序的穩定性，穩定性好的排序是：冒泡、插入、歸并，保證相等的值的相對順序不變。

算法庫里有一個穩定的排序（底層是歸并，用其他的穩定的排序效率太低）：

解法二：不用stable_sort有什么辦法解決呢？將map統計出的次數的數據放到vector中排序，或者放到priority_queue中來選出前k個。利用仿函數強行控制次數相等的，字典序小的在前面。

四、代碼

解法一：

class Solution {
public:// stable_sort與庫里的pair比較行為不符，自定義比較器——定制仿函數struct Compare{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 (auto& e : words){countMap[e]++;}// 排降序 —— map的數據倒過來，字典序排過了vector<pair<string, int>> v(countMap.begin(), countMap.end());// 仿函數控制降序stable_sort(v.begin(), v.end(), Compare());/* LeetCode平臺支持打印 *///for (auto& e : v)//{//    cout << e.first << ":" << e.second << endl;//}vector<string> ret;for (int i = 0; i < k; ++i){ret.push_back(v[i].first);}return ret;}
};

解法二：

class Solution {
public:// stable_sort與庫里的pair比較行為不符，自定義比較器——定制仿函數struct Compare{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 (auto& e : words){countMap[e]++;}// 排降序vector<pair<string, int>> v(countMap.begin(), countMap.end());// 仿函數控制降序，仿函數控制次數相等，字典序小的在前面sort(v.begin(), v.end(), Compare());// 取前k個vector<string> ret;for (int i = 0; i < k; ++i){ret.push_back(v[i].first);}return ret;}
};

class Solution {
public:// stable_sort與庫里的pair比較行為不符，自定義比較器——定制仿函數struct Compare{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 (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> ret;for (int i = 0; i < k; i++){ret.push_back(p.top().first);p.pop();}return ret;}
};