微网站后台怎么注册,演出公司网站建设,如何开一家自己的公司,做产品网站营销推广前k个高频单词 题目思路代码代码讲解 题目 思路
通过统计字符串的出现次数#xff0c;并根据出现次数和字典序对字符串进行排序#xff0c;找出出现频率最高的前k个字符串。使用一个自定义的仿函数作为排序的比较函数#xff0c;通过map容器进行统计#xff0c;然后将结果… 前k个高频单词 题目思路代码代码讲解 题目 思路
通过统计字符串的出现次数并根据出现次数和字典序对字符串进行排序找出出现频率最高的前k个字符串。使用一个自定义的仿函数作为排序的比较函数通过map容器进行统计然后将结果存储在向量中返回 代码 //仿函数struct kvCom{bool operator()(const pairstring,int p1,const pairstring,int p2){return p1.secondp2.second || (p1.secondp2.second p1.firstp2.first);}};vectorstring topKFrequent(vectorstring words, int k) {mapstring,int CountMap ;for (auto e : words){CountMap[e];}//sort中的支持的是随机迭代器而map是双向迭代器所有将map中的数据存到vector中再用sortvectorpairstring,int sortV(CountMap.begin(),CountMap.end());//稳定的sort//stable_sort(sortV.begin(),sortV.end(),kvCom());sort(sortV.begin(),sortV.end(),kvCom());//对次数排序vectorstring ret;for (int i0;ik;i){ret.push_back(sortV[i].first);}return ret;}代码讲解 struct kvCom{bool operator()(const pairstring,int p1,const pairstring,int p2){return p1.secondp2.second || (p1.secondp2.second p1.firstp2.first);}};struct kvCom定义了一个结构体kvCom它是一个仿函数function object。仿函数是重载了函数调用操作符operator()的对象可以像函数一样被调用。在这个结构体中重载了operator()用于定义对存储字符串-整数对的pair进行比较的规则。bool operator()(const pairstring,int p1,const pairstring,int p2)这是kvCom结构体中的函数调用操作符的重载。它接受两个参数都是pairstring,int类型的引用。函数的目的是比较这两个pair对象的大小返回一个布尔值表示两个对象的大小关系。具体的比较规则如下 首先比较第二个元素即整数部分的大小如果p1的第二个元素大于p2的第二个元素则返回true否则返回false。 如果两个元素的第二个元素相等那么比较第一个元素即字符串部分的大小如果p1的第一个元素小于p2的第一个元素则返回true否则返回false。 vectorstring topKFrequent(vectorstring words, int k) {mapstring,int CountMap ;for (auto e : words){CountMap[e];}//sort中的支持的是随机迭代器而map是双向迭代器所有将map中的数据存到vector中再用sortvectorpairstring,int sortV(CountMap.begin(),CountMap.end());//稳定的sort//stable_sort(sortV.begin(),sortV.end(),kvCom());sort(sortV.begin(),sortV.end(),kvCom());//对次数排序vectorstring ret;for (int i0;ik;i){ret.push_back(sortV[i].first);}return ret;}mapstring,int CountMap定义了一个map容器CountMap用于统计每个字符串在words中出现的次数。map是一个关联容器它存储了键-值对其中键是唯一的即每个字符串只会在map中出现一次值表示字符串出现的次数。 for (auto e : words)遍历words中的每个字符串使用引用e来获取字符串的引用。这样可以避免在循环中对字符串进行拷贝提高性能。 CountMap[e]将当前遍历到的字符串e作为键在CountMap中查找对应的值并将其加1。如果e在CountMap中不存在则会自动插入一个键为e值为0的键-值对然后将值加1。 vectorpairstring,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 i0;ik;i)从排序后的向量sortV中取出前k个字符串。 ret.push_back(sortV[i].first)将第i个字符串的第一个元素即字符串本身添加到结果向量ret中。 return ret返回存储了出现频率最高的前k个字符串的向量ret。 本题完
