题目
思路
通过统计字符串的出现次数，并根据出现次数和字典序对字符串进行排序，找出出现频率最高的前k个字符串。使用一个自定义的仿函数作为排序的比较函数，通过map容器进行统计，然后将结果存储在向量中返回
代码
//仿函数 struct kvCom { bool operator()(const pair<string,int>& p1,const pair<string,int>& p2) { return p1.second>p2.second || (p1.second==p2.second && p1.first<p2.first); } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string,int> CountMap ; for (auto &e : words) { CountMap[e]++; } //sort中的支持的是随机迭代器，而map是双向迭代器，所有将map中的数据存到vector中再用sort vector<pair<string,int>> sortV(CountMap.begin(),CountMap.end()); //稳定的sort //stable_sort(sortV.begin(),sortV.end(),kvCom()); sort(sortV.begin(),sortV.end(),kvCom());//对次数排序 vector<string> ret; for (int i=0;i<k;i++) { ret.push_back(sortV[i].first); } return ret; }
代码讲解
struct kvCom { bool operator()(const pair<string,int>& p1,const pair<string,int>& p2) { return p1.second>p2.second || (p1.second==p2.second && p1.first<p2.first); } };
- struct kvCom：定义了一个结构体kvCom，它是一个仿函数（function object）。仿函数是重载了函数调用操作符operator()的对象，可以像函数一样被调用。在这个结构体中，重载了operator()，用于定义对存储字符串-整数对的pair进行比较的规则。
- bool operator()(const pair<string,int>& p1,const pair<string,int>& p2)：这是kvCom结构体中的函数调用操作符的重载。它接受两个参数，都是pair<string,int>类型的引用。函数的目的是比较这两个pair对象的大小，返回一个布尔值表示两个对象的大小关系。具体的比较规则如下：
首先比较第二个元素（即整数部分）的大小，如果p1的第二个元素大于p2的第二个元素，则返回true，否则返回false。
如果两个元素的第二个元素相等，那么比较第一个元素（即字符串部分）的大小，如果p1的第一个元素小于p2的第一个元素，则返回true，否则返回false。
vector<string> topKFrequent(vector<string>& words, int k) { map<string,int> CountMap ; for (auto &e : words) { CountMap[e]++; } //sort中的支持的是随机迭代器，而map是双向迭代器，所有将map中的数据存到vector中再用sort vector<pair<string,int>> sortV(CountMap.begin(),CountMap.end()); //稳定的sort //stable_sort(sortV.begin(),sortV.end(),kvCom()); sort(sortV.begin(),sortV.end(),kvCom());//对次数排序 vector<string> ret; for (int i=0;i<k;i++) { ret.push_back(sortV[i].first); } return ret; }
- map<string,int> CountMap：定义了一个map容器CountMap，用于统计每个字符串在words中出现的次数。map是一个关联容器，它存储了键-值对，其中键是唯一的，即每个字符串只会在map中出现一次，值表示字符串出现的次数。
- for (auto &e : words)：遍历words中的每个字符串，使用引用&e来获取字符串的引用。这样可以避免在循环中对字符串进行拷贝，提高性能。
- CountMap[e]++：将当前遍历到的字符串e作为键，在CountMap中查找对应的值，并将其加1。如果e在CountMap中不存在，则会自动插入一个键为e，值为0的键-值对，然后将值加1。
- vector<pair<string,int>> sortV(CountMap.begin(),CountMap.end())：sort中的支持的是随机迭代器，而map是双向迭代器，所有将map中的数据存到vector中再用sort。使用CountMap中的数据初始化一个存储字符串-整数对的sortV。这样做是为了将CountMap中的数据按照出现次数进行排序。
- sort(sortV.begin(),sortV.end(),kvCom())：对sortV中的元素按照指定的排序规则进行排序。这里使用了kvCom结构体的对象作为比较函数，用来定义排序规则。排序的规则是按照字符串出现次数的降序排列，如果出现次数相同，则按照字符串的字典序（升序）进行排列。
- vector ret：定义一个字符串向量ret，用于存储结果。
- for (int i=0;i<k;i++)：从排序后的向量sortV中取出前k个字符串。
- ret.push_back(sortV[i].first)：将第i个字符串的第一个元素（即字符串本身）添加到结果向量ret中。
- return ret：返回存储了出现频率最高的前k个字符串的向量ret。
（本题完）
