本公司现在要给公司员工发波福利,在员工工作时间会提供大量的水果供员工补充营养。由于水果种类比较多,但是却又不知道哪种水果比较受欢迎,然后公司就让每个员工报告了自己最爱吃的k种水果,并且告知已经将所有员工喜欢吃的水果存储于一个数组中。然后让我们统计出所有水果出现的次数,并且求出大家最喜欢吃的前k种水果。
void GetFavoriteFruit(const vector& fruits,size_t k);
ps:要求打印出最喜欢的水果,并且效率尽可能的高。
提示:尽量STL的容器和算法,这样能更快速高效的实现。
已知一个vector fruits存放每个员工填写的自己喜欢的k种水果。
(1)首先要遍历该vector,统计出每种水果的数量。可以借助STL容器中的map<水果,水果count>;
(2)排序,找最前k种水果, 用STL中的优先级队列、堆或者set, 将map存放到vector中进行sort排序,
注:下面代码没有考虑k值不满足的情况,比如水果种类不够k k <=0 的情况
1、优先级队列
void GetFavoriteFruit(const vector<string>& fruits, size_t k) { //统计各种水果的个数 map<string, int> fruits_count; for (int i = 0; i < fruits.size(); ++i) { fruits_count[fruits[i]]++; } //排序,找最前k种水果 struct Compare //函数对象,堆中的元素比较的方式 { bool operator()(map<string, int>::iterator it1, map<string, int>::iterator it2) { return it1->second < it2->second; } }; //1优先级队列,其实也是堆 //优先级队列(大堆),type,container(不能为list),compare,默认为< priority_queue<map<string, int>::iterator, vector<map<string, int>::iterator>, Compare> q; map<string, 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、set
void GetFavoriteFruit2(const vector<string>& fruits, size_t k) { //统计各种水果的个数 map<string, int> fruits_count; for (int i = 0; i < fruits.size(); ++i) { fruits_count[fruits[i]]++; } struct Compare //函数对象,堆中的元素比较的方式 { bool operator()(map<string, int>::iterator it1, map<string, int>::iterator it2) { return it1->second > it2->second; } }; set<map<string, int>::iterator, Compare> s; map<string, int>::iterator it = fruits_count.begin(); while (it != fruits_count.end()) { s.insert(it); ++it; } // set<map<string, int>::iterator, Compare>::iterator ite = s.begin(); int count = 0; while (ite != s.end() && count < k) { cout << "水果:" << (*ite)->first << "水果count :" << (*ite)->second << endl; ++ite; ++count; } }3、堆
void GetFavoriteFruit2(const vector<string>& fruits, size_t k) { //统计各种水果的个数 map<string, int> fruits_count; for (int i = 0; i < fruits.size(); ++i) { fruits_count[fruits[i]]++; } map<string, int>::iterator it = fruits_count.begin(); vector<map<string, int>::iterator> vec; while (it != fruits_count.end()) { vec.push_back(it); ++it; } //建堆 struct Compare { bool operator()(map<string, int>::iterator it1, map<string, int>::iterator it2) { return it1->second < it2->second; } }; make_heap(vec.begin(), vec.end(), Compare()); //找堆中前k个 vector<map<string, int>::iterator>::iterator iter = vec.begin(); int count = 0; while (iter != vec.end() && count <k) { cout << "水果:" << (*iter)->first << "水果count :" << (*iter)->second << endl; pop_heap(vec.begin(), vec.end(), Compare()); ++count; } }