某公司将所有员工喜欢吃的水果存储于一个数组中。要求：统计出所有水果出现的次数，并且求出大家最喜欢吃的前k种水果。 1、统计所有水果出现的次数，我们可以使用map<string, int>结构，string存储水果名，int存储水果数目； 2、求大家最喜欢吃的前k种水果，我们可以使用vector<map<string, int>::iterator>结构存放每一种水果，然后通过iterator->second对vector进行排序，就可以找到前K种水果啦。 具体实现：
//统计出所有水果出现的次数，并且求出大家最喜欢吃的前k种水果。 #include<iostream> #include<stdlib.h> #include<vector> #include <string> #include<map> #include<algorithm> using namespace std; void GetFirst_K_Fruit(const vector<string> &fruit,size_t k) { map<string, int> fruit_count;//记录水果及其数量 //=============效率低，每次插入都要遍历map========== //for (size_t idx = 0; idx < fruit.size(); ++idx) //{ // map<string, int>::iterator it = fruit_count.find(fruit[idx]); // if (it != fruit_count.end()) // it->second++; // else // fruit_count.insert(make_pair(fruit[idx],1)); //} //================================================== //==================进行优化======================== //原理：map.insert()的返回值是pair<map::iterator,bool>键值对。不管是否插入成功，它都能返回当前元素的迭代器 //那么我们可以直接插入，然后对其返回值进行判断，返回值第二个参数是true，表示插入成功，为flase，表示插入失败 pair<map<string, int>::iterator, bool> ret; for (size_t idx = 0; idx < fruit.size(); ++idx) { ret = fruit_count.insert(make_pair(fruit[idx], 1)); if (ret.second == false) ret.first->second++; } vector<map<string, int>::iterator> v;//定义一个vector存放map的迭代器 map<string, int>::iterator it = fruit_count.begin(); while (it != fruit_count.end()) { v.push_back(it); it++; } struct Compare//仿函数，采用降序 { bool operator ()(map<string, int>::iterator it1, map<string, int>::iterator it2) { return it1->second > it2->second; } }; sort(v.begin(), v.end(),Compare()); for (size_t idx = 0; idx < k; ++idx) { cout << v[idx]->first << " "; } cout << endl; } int main() { vector<string> v1 = {"apple", "orange", "banana", "orange", "strawberry", "watermelon", "apple", "orange", "banana", "orange", "strawberry", "watermelon", "strawberry", "watermelon" ,"pear","straberry"}; GetFirst_K_Fruit(v1, 3); system("pause"); return 0; }