题目：
本公司现在要给公司员工发波福利，在员工工作时间会提供大量的水果供员工补充营养。由于水果种类比较多，但是却又不知道哪种水果比较受欢迎，然后公司就让每个员工报告了自己最爱吃的k种水果，并且告知已经将所有员工喜欢吃的水果存储于一个数组中。然后让我们统计出所有水果出现的次数，并且求出大家最喜欢吃的前k种水果。
void AdjustDown(vector<pair<string, int>* >& rel, size_t index) { size_t left = index * 2 + 1; while (left < rel.size()) { pair<string, int> *child = rel[left]; if (left + 1 < rel.size() && child->second > rel[left + 1]->second) { left++; child = rel[left]; } pair<string, int> *parent = rel[index]; if (parent->second > child->second) { rel[left] = parent; rel[index] = child; index = left; left = index * 2 + 1; } else break; } } void GetFavoriteFruit( vector<string>& fruits, size_t k) { map<string, int> fru; vector<string>::iterator itStart = fruits.begin(); while (itStart != fruits.end()) { const char *c = (*itStart).c_str(); fru[c]++; itStart++; } //水果和其出现的次数保存在fru中 vector<pair<string,int>* > rel; /*容器调用resize()函数后，所有的空间都已经初始化了，所以可以直接访问。 而reserve()函数预分配出的空间没有被初始化，所以不可访问。*/ rel.reserve(k); //size_t i = 0; map<string, int>::iterator mapIt = fru.begin(); size_t i = 0; pair<string, int> *cur = NULL; for (; i < k; i++) { cur = new pair<string, int>(mapIt->first, mapIt->second); rel.push_back(cur); mapIt++; } for (int j = (k - 2) / 2; j >= 0; j--) { AdjustDown(rel, j); } while (mapIt != fru.end()) { if (rel[0]->second < mapIt->second) { cur = new pair<string, int>(mapIt->first, mapIt->second); rel[0] = cur; AdjustDown(rel, 0); } mapIt++; } for (size_t i = 0; i < rel.size(); i++) { fruits[i] = rel[i]->first; } fruits.resize(k); } void TestFindKElem() { vector<string> fr; fr.push_back("苹果"); fr.push_back("香蕉"); fr.push_back("香蕉"); fr.push_back("香蕉"); fr.push_back("香蕉"); fr.push_back("西瓜"); fr.push_back("西瓜"); fr.push_back("西瓜"); fr.push_back("西瓜"); fr.push_back("西瓜"); fr.push_back("西瓜"); fr.push_back("苹果"); fr.push_back("草莓"); fr.push_back("草莓"); fr.push_back("草莓"); fr.push_back("草莓"); fr.push_back("草莓"); fr.push_back("草莓"); fr.push_back("草莓"); fr.push_back("草莓"); fr.push_back("草莓"); fr.push_back("草莓"); fr.push_back("葡萄"); fr.push_back("荔枝"); fr.push_back("荔枝"); fr.push_back("荔枝"); fr.push_back("芒果"); fr.push_back("芒果"); fr.push_back("芒果"); fr.push_back("芒果"); fr.push_back("芒果"); fr.push_back("芒果"); fr.push_back("芒果"); GetFavoriteFruit(fr, 4); }
