电脑版网站转手机版怎么做,全网分销平台,网站程序引擎,展示型网站包含哪些模块1、问题 本公司现在要给公司员工发波福利#xff0c;在员工工作时间会提供大量的水果供员工补充营养。由于水果种类比较多#xff0c;但是却又不知道 哪种水果比较受欢迎#xff0c;然后公司就让每个员工报告了自己最爱吃的k种水果#xff0c;并且告知已经将所有员工喜欢吃…1、问题 本公司现在要给公司员工发波福利在员工工作时间会提供大量的水果供员工补充营养。由于水果种类比较多但是却又不知道 哪种水果比较受欢迎然后公司就让每个员工报告了自己最爱吃的k种水果并且告知已经将所有员工喜欢吃的水果存储于一个数组中。 然后让我们统计出所有水果出现的次数并且求出大家最喜欢吃的前k种水果。 void GetFavoriteFruit(const vector fruitssize_t k); ps:要求打印出最喜欢的水果并且效率尽可能的高。 提示尽量STL的容器和算法这样能更快速高效的实现。 2、问题分析 已知一个vector fruits存放每个员工填写的自己喜欢的k种水果。 (1)首先要遍历该vector统计出每种水果的数量。可以借助STL容器中的map水果水果count (2)排序找最前k种水果 1用STL中的优先级队列 #include iostream
#include map
#include vector
#include string
#include stdlib.h
//#include algorithm
#include queueusing namespace std;void GetFavoriteFruit(const vectorstring fruits, size_t k)
{//统计各种水果的个数mapstring, int fruits_count;for (int i 0; i fruits.size(); i){fruits_count[fruits[i]];}//排序找最前k种水果struct Compare //函数对象堆中的元素比较的方式{bool operator()(mapstring, int::iterator it1, mapstring, int::iterator it2){return it1-second it2-second;}};//优先级队列大堆typecontainer(不能为list)compare默认是 priority_queuemapstring, int::iterator, vectormapstring, int::iterator, Compare q;mapstring, int::iterator it fruits_count.begin();while (it ! fruits_count.end()){q.push(it);it;}for (int i 0; i k; i){cout q.top()-first q.top()-second endl;q.pop();}
}2最大堆 #include iostream
#include map
#include vector
#include string
#include stdlib.h
#include algorithmusing namespace std;
//使用堆
void GetFavoriteFruit(const vectorstring fruits, size_t k)
{//统计水果数量mapstring, int fruits_count;/*原理map.insert()的返回值是pairmap::iterator,bool键值对。不管是否插入成功它都能返回当前元素的迭代器那么我们可以直接插入然后对其返回值进行判断返回值第二个参数是true表示插入成功为flase表示插入失败*/pairmapstring, int::iterator, bool ret;for(size_t i 0; i fruits.size(); i){ret fruits_count.insert(make_pair(fruits[i], 1));if(ret.second false)ret.first-second;}vectormapstring, int::iterator v;mapstring, int::iterator it fruits_count.begin();while(it ! fruits_count.end()){v.push_back(it);it;}struct Compare{bool operator()(mapstring, int::iterator it1, mapstring, int::iterator it2){return it1-second it2-second; }};make_heap(v.begin(), v.end(),Compare());//找出大堆中的前k个vectormapstring, int::iterator::iterator iter v.begin();for(size_t i 0; i k; i){cout(*iter)-first : (*iter)-secondendl;pop_heap(v.begin(), v.end(),Compare());v.pop_back();}
}将map存放到vector中进行sort排序 #include iostream
#include map
#include vector
#include string
#include stdlib.h
#include algorithmusing namespace std;
//使用sort排序
void GetFavoriteFruit(const vectorstring fruits, size_t k)
{//统计水果数量mapstring, int fruits_count;for(size_t i 0; i fruits.size(); i){fruits_count[fruits[i]];}vectormapstring, int::iterator v;mapstring, int::iterator it fruits_count.begin();while(it ! fruits_count.end()){v.push_back(it);it;}struct Compare{bool operator()(mapstring, int::iterator it1, mapstring, int::iterator it2){return it1-second it2-second; }};sort(v.begin(), v.end(), Compare());for(size_t i 0; i k; i){coutv[i]-first : v[i]-secondendl;}
}set(也可用来排序但是会去掉重复故有缺陷比如两种水果被选次数相同会忽略掉一种打印数量相对更少的) #include iostream
#include set
#include map
#include string
#include stdlib.h
#include vectorusing namespace std;void GetFavoriteFruit(const vectorstring fruits, size_t k)
{//统计各种水果的个数mapstring, int fruits_count;for (int i 0; i fruits.size(); i){fruits_count[fruits[i]];}struct Compare //函数对象堆中的元素比较的方式{bool operator()(mapstring, int::iterator it1, mapstring, int::iterator it2){return it1-second it2-second;}};setmapstring, int::iterator, Compare s;mapstring, int::iterator it fruits_count.begin();while (it ! fruits_count.end()){s.insert(it);it;}//setmapstring, int::iterator, Compare::iterator ite s.begin();int count 0;while (ite ! s.end() count k){cout (*ite)-first (*ite)-second endl;ite;count;}
}
