三.题目练习
力扣：前K个高频单词
力扣链接：力扣
看到这道题大家应该首先想到的就是map了吧，毕竟题目已经很明显的说了KV键值对，下面我们说一下思路：首先我们用mp的[]功能统计出每个单词出现的次数以及对应的每个单词，然后我们将前K个这样的单词放入向量中，然后打印即可：
class Solution { public: struct compare { bool operator()(const pair<string,int>& k1,const pair<string,int>& k2) { return k1.second>k2.second; } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string,int> mp; for (auto& e:words) { mp[e]++; } vector<pair<string,int>> v(mp.begin(),mp.end()); sort(v.begin(),v.end(),compare()); vector<string> result; for (int i = 0;i<k;i++) { result.push_back(v[i].first); } return result; } };
首先我们用一个map来计算单词以及单词的次数，然后用一个vector来保存这些键值对（vector的类型一定是pair），然后我们用sort函数排序vector,由于pair默认的排序方式是以K值进行排序的，所以我们必须写一个仿函数来用键值对中的value值比较，比较完成后我们用另一个vector来接收前K个字符串，最后我们只需要返回string即可所以是v[i].first。但是如果我们发现没有通过，如下图：
发现错误的原因是单词的顺序不对，当出现相同次数的单词需要用字典序来排序，所以这个时候我们就想到了排序的稳定性，如果一个排序稳定的话相同的值的相对顺序是不变的，本题给的测试列表本来也是按照字典序排好的，所以我们直接换一个稳定排序就解决了，在算法中有一个稳定排序：
下面我们就换上这个稳定排序：
这样我们就通过了，那么如果我们还有其他办法解决刚刚的顺序问题吗？答案是当然有，要知道我们写仿函数的目的就是为了控制比较方式：
当然我们也可以用我们刚刚学的的set来进行比较，因为我们的set和map也是支持控制比较方式的：
class Solution { public: struct compare { bool operator()(const pair<string,int>& k1,const pair<string,int>& k2) const { return k1.second>k2.second||(k1.second==k2.second)&&k1.first<k2.first; } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string,int> mp; for (auto& e:words) { mp[e]++; } set<pair<string,int>,compare> st(mp.begin(),mp.end()); vector<string> v; auto it = st.begin(); while (k--) { v.push_back(it->first); ++it; } return v; } };
在这里大家要注意：
set中对于仿函数用的是模板，模板我们必须传类型所以我们写set的时候写的compare，像sort就不一样了：
我们可以看到sort中传的是仿函数对象，所以我们使用的时候用了匿名对象compare().当然上面的代码中我们写仿函数一定要在后面加上const，因为有些测试用例会有const对象，如果没写const会编译报错。
总结
学数据结构就如同我们打怪升级一般，从一开始的单链表到二叉树，每一次的难度都是层层递进的，到了map这边下一篇我们要讲的AVL树难度要比二叉树搜索树难了不止一点，但是只要大家有着面对困难打败困难的心就一定可以成为屠龙勇士~
