函数原型
void GetFavoriteFruit(const vector& fruits，size_t k);
统计次数
//仿函数 struct Geater { bool operator()(map<string,int>::iterator l,map<string,int>::iterator r) { return (l->second) > (r->second); } };第一种方法
map<string, int> dict; int i = 0; //统计次数 //这种先看它在不在，在的话在基础上加一，不在直接插入并把次数置为1.需要遍历2次 for (i = 0; i < fruits.size(); i++) { map<string, int>::iterator ret = dict.find(fruits[i]); if (ret != dict.end()) { ret->second++; } dict.insert(pair<string, int>(fruits[i], 1)); }第二种方法
for (i = 0; i < fruits.size(); i++) { pair<map<string, int>::iterator, bool> ret = dict.insert(make_pair(fruits[i], 1)); if (ret.second == false) { ret.first->second++; } }找出前k种 1.排序
vector<map<string, int>::iterator> ve; map<string, int>::iterator it = dict.begin(); while (it != dict.end()) { ve.push_back(it); it++; } sort(ve.begin(), ve.end(), Geater()); for (i = 0; i < k;i++) { cout << ve[i]->first<<":" <<ve[i]->second<< " "; } cout << endl;2.利用堆是实现（建小堆）
//第二种方法利用堆排序，要找前k个，就可以用前k个建一个小堆，然后再插入的数比堆顶大，就往近插入，调整堆为小堆，继续插入， //直到遍历结束，这个堆中保存的数就是前k个。 for (i = 0; i < k; i++) { ve.push_back(it); it++; } make_heap(ve.begin(), ve.end(), Geater());//建一个k大小的小堆 while (it != dict.end()) { if (it->second>ve[0]->second)//如果大于堆顶，就插入重新建堆 { ve[0] = it; } it++; make_heap(ve.begin(), ve.end(), Geater()); } cout << "topk" << endl; for (i = 0; i < k; i++) { cout << ve[0]->first << ":" << ve[0]->second << endl; } }3 优先级队列
优先级队列每次查找或删除的元素都是权值最大或优先级最高的。
template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue; struct Compare { bool operator()(map<string, int>::iterator l, map<string, int>::iterator r) { return (l->second) < (r->second); } }; priority_queue<map<string, int>::iterator, vector<map<string, int>::iterator>,Compare> q; map<string, int>::iterator it = dict.begin(); while (it != dict.end()) { q.push(it); it++; } for (i = 0; i < k; i++) { cout << q.top()->first << ":" << q.top()->second << endl; q.pop(); } }