面试题--本公司现在要给公司员工发波福利，在员工工作时间会提供大量的水果供员工补充营养。由于水果种类比较多，但是却又不知道哪种水果比较受欢迎，然后公司就让每个员工报告了自己最爱吃的k种水果

本文主要是介绍面试题--本公司现在要给公司员工发波福利，在员工工作时间会提供大量的水果供员工补充营养。由于水果种类比较多，但是却又不知道哪种水果比较受欢迎，然后公司就让每个员工报告了自己最爱吃的k种水果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本公司现在要给公司员工发波福利，在员工工作时间会提供大量的水果供员工补充营养。由于水果种类比较多，但是却又不知道哪种水果比较受欢迎，然后公司就让每个员工报告了自己最爱吃的k种水果，并且告知已经将所有员工喜欢吃的水果存储于一个数组中。然后让我们统计出所有水果出现的次数，并且求出大家最喜欢吃的前k种水果。

void GetFavoriteFruit(const vector& fruits，size_t k);

思路一：
排序，但是我们又不知道有多少种水果，如果水果很多。排序将会带来很大的时间复杂度和空间复杂度。

那么，这道题应该怎么做呢？
当然，首选的应该是红黑树了，并且需要的是K/V结构的红黑树，K来存储水果的名称，V来存储这个水果出现的次数。
可是红黑树结构复杂，在面试的时候想写出来不是那么容易，所以这里有了STL两个容器，map和set。
set和map这两个容器的底层都是用红黑树来实现的，并且他们都具有防冗余的特性（被插入的数据如果在容器中已经出现，那么插入失败），他两的唯一区别就是set是一个K结构，而map是一个K/V结构。

map原型：

template < class Key,                                     class T,                                         class Compare = less<Key>,                     class Alloc = allocator<pair<const Key,T> >    > class map;

Key:这个就是我刚才说的K/V结构中的K
T:这是K/V结构中的V。
Compare:这是一个接受仿函数类型的参数，可以控制map是一个升序的还是降续的(不传这个参数时，默认是升序)。
Alloc：空间配置器。

那么这个题该怎么解决？
定义一个map，然后将数组中所有的元素插入到map中，在插入前先使用find()来查找存在不存在，如果不存在则插入，如果存在，则利用find返回值来对找到的元素的V进行+1操作。（其中fruits是水果数组）

map<string, int> fruitCount;//创建map对象  
for (int i = 0; i < sizeof(fruits) / sizeof(fruits[0]); ++i)  
{  map<string, int>::iterator it = fruitCount.find(fruits[i]);//创建map迭代器  if (it != fruitCount.end())//先查找看该字符数组内是否存在该字符串  {  it->second++;//给该类对象的计数+1   }  else  {  fruitCount.insert(pair<string, int>(fruits[i], 1));  }  
}

缺点：如果map中没有要插入的这个水果，则需要遍历两次map。

思路二：只遍历一次map
insert的返回值pair。既然不管是否插入成功，它都能返回我们需要的这个元素的迭代器。那么，我们可以先插入，然后对其返回值进行保存，如果该返回值得第二个参数是true，表示插入成功，不进行其他操作，如果为flase，表示插入失败，那么其返回的第一个参数将会带回已经存在的这个被插入元素的迭代器，当然轻而易举就可以通过迭代器拿到这个元素的第二个参数V。

void CalculateFruitCount(map<string,int>& m, string fruits[], size_t size)  
{  for (size_t i = 0; i < size; i++)  {  //m[fruits[i]]++;    //map中有operator[]的重载,其内容等同于下边代码  pair<map<string, int>::iterator, bool> ret;  ret = m.insert(make_pair(fruits[i], 1));  if (ret.second == false)  ret.first->second++;  }  
}

现在走到这里已经全部插入了，那接下来我们就需要找前K个最喜欢的水果了。

思路一：
将统计好的数据全部放入一个vector中，并且利用排序算法sort进行排序。而其默认为升序，最大的则位于数组后边，但是我们并不知道vector有多大。所以，我们采用降续，这样最大的永远在vector的前列.

void GetBeginOfThreeFruits(map<string, int>& m, vector<map<string, int>::iterator>& v)  //按照水果出现的次数降续存储于v中  
{  map<string, int>::iterator it = m.begin();  while (it != m.end())  {  v.push_back(it);  it++;  }  struct Compare   //仿函数（降续）  {  bool operator()(map<string, int>::iterator l, map<string, int>::iterator r)  {  return l->second > r->second;  }  };  sort(v.begin(), v.end(),Compare());  
}

思路二：给一个堆，这个堆只要K个大小。
因为找出现次数最多的，所以这里给一个小堆。堆顶元素为最小的数。每一次新进来的数字和堆顶比较，如果比堆顶小则不要。比堆顶大则把堆顶pop，把这个元素插入再重新排堆。

void GetBeginOfNFruits(map<string, int>& m, size_t n, vector<map<string,int>::iterator>& v)  
{  map<string, int> ::iterator it = m.begin();  for (size_t i = 0; i < n; ++i)  {  v.push_back(it);  it++;  }  struct Compare  //堆算法默认是大堆，此处需要仿函数将其改为小堆  {  bool operator()(map<string, int>::iterator l, map<string, int>::iterator r)  {  return l->second > r->second;  //小堆  }  };  make_heap(v.begin(), v.end(), Compare());  while (it != m.end())  {  if (it->second > v.front()->second)  {  pop_heap(v.begin(), v.end(), Compare());  v.pop_back();  v.push_back(it);  push_heap(v.begin(), v.end(), Compare());  }  it++;  }  
}