题目链接

题目描述：

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

小根堆

  1. 遍历数组，哈希表录入频率
  2. 遍历哈希表，维护一个出现频率前k多的小根堆
  3. 优先队列已满，需要判断当前元素的频率是否大于优先队列的最小频率元素的频率，如果大于，则替换。
  4. 优先队列未满，进队即可

  注意：c++ 优先队列默认大根堆，设置时需要priority_queue< pair<int,int> , vector< pair<int,int> >, greater< pair<int,int> > >实现小根堆。

代码

  1. class Solution {
  2. public:
  3.     vector<int> topKFrequent(vector<int>& nums, int k) {
  4.         unordered_map<int,int> record;  //(元素，频率)
  5.         //遍历数组，录入频率
  6.         for(int i = 0; i < nums.size(); i++){
  7.             record[nums[i]]++;
  8.         }
  9.         int n = record.size();
  11.         //扫描record。维护当前出现频率最多的k个元素
  12.         //最小堆。如果当前元素的频率大于优先队列中最小频率元素的频率，则替换
  13.         //优先队列中，按频率排序，所以数据对是(频率，元素)形式
  14.         priority_queue< pair<int,int> , vector< pair<int,int> >, greater< pair<int,int> > > pq;
  15.         for(auto iter = record.begin(); iter != record.end(); iter++){
  16.             if(k == pq.size()){ //队列已满
  17.                 if(iter->second > pq.top().first){
  18.                     pq.pop();
  19.                     pq.push(make_pair(iter->second,iter->first));
  20.                 }
  21.             }
  22.             else{
  23.                 pq.push(make_pair(iter->second,iter->first));
  24.             }
  25.         }
  27.         vector<int> result;
  28.         while(!pq.empty()){
  29.             result.push_back(pq.top().second);
  30.             pq.pop();
  31.         }
  32.         return result;
  33.     }
  34. };

大根堆

  通常情况下求前k大用小根堆，求前k小用大根堆。我们知道，小根堆的方法的时间复杂度为O(nlogk)，如果k与n很接近呢？如果我非要用大根堆呢？其实也是可以的，只是需要转换一下思路即可。既然让我们求前k大，那么我们是不是可以转换一下思路求前n-k小呢？当然是可以的，而且c++的堆默认是大根堆，这样会稍微省一下声明的麻烦。但最后两者的执行用时一样，哭了～～
  注意：一定要考虑n == k的情况，不然你就会像我一样卡在测试用例nums = [1], k = 1上，错误信息为Char 17: runtime error: reference binding to null pointer of type 'const struct pair' (stl_iterator.h)。其实很好理解：对于该测试用例，n == k会使得一开始if( (n - k) == (int)pq.size() )就通过，那么在初始条件下，就会进行取堆顶和出堆的操作，显然队列为空，不能访问。

代码

  1. class Solution {
  2. public:
  3.     vector<int> topKFrequent(vector<int>& nums, int k) {
  5.         unordered_map<int,int> record;  //(元素，频率)
  6.         //遍历数组，录入频率
  7.         for(int i = 0; i < nums.size(); i++){
  8.             record[nums[i]]++;
  9.         }
  10.         int n = record.size();
  12.         vector<int> result;
  13.         if(n != k){ // 如果 n == k，根据题意，直接统计 record 中的元素就好了
  15.             //扫描record。维护当前出现频率最少的n-k个元素
  16.             //最大堆。如果当前元素的频率小于优先队列中最大频率元素的频率，则替换
  17.             //优先队列中，按频率排序，所以数据对是(频率，元素)形式
  18.             priority_queue< pair<int,int> > pq;
  19.             for(auto iter = record.begin(); iter != record.end(); iter++){
  20.                 if((n - k) == (int)pq.size()){ //队列已满
  21.                     if(iter->second < pq.top().first){
  22.                         pq.pop();
  23.                         pq.push(make_pair(iter->second,iter->first));
  24.                     }
  25.                 }
  26.                 else{
  27.                     pq.push(make_pair(iter->second,iter->first));
  28.                 }
  29.             }
  31.             while(!pq.empty()){
  32.                 record.erase(pq.top().second);
  33.                 pq.pop();
  34.             }
  35.         }
  37.         for(auto iter : record){
  38.             result.push_back(iter.first);
  39.         }
  40.         return result;
  41.     }
  42. };

如果有错误或者不严谨的地方，请务必给予指正，十分感谢。