LeetCode 347. Top K Frequent Elements

题目描述

知识点

堆排序

结果

实现

码前思考

1. 解题分为两个步骤：
   ① 使用hash的思想，将数字与数字出现的次数对应上；
   ② 按照数字出现的次数，选出排名前k个的。
2. 这是一个求前k个的题目，之前说看见求前k个的题目要第一时间想到堆，所以这里使用堆。
3. 这里说我们的时间复杂度一定要比$O(NlongN)$O(NlongN)要好，所以我们这里不能用简单的快速排序或者sort()了。使用堆，因为堆是解决这种前k个的良好方法，可以做到这个时间复杂度；

代码实现

//如果不是出现在堆排序的题目里面，我很难想到要用堆排序
//还有就是使用堆，真的可以吗？
//首要要记录所有的数字出现的次数，时间复杂度为O(n)，使用map存储
//数组不能为空，而且k是有效的
struct node{
    int val;
    int cnt;
    node(int _val,int _cnt):val(_val),cnt(_cnt){}
    friend bool operator < (node a,node b){
        return a.cnt < b.cnt;
    }
};

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int,int> mp;
        priority_queue<node> q;
        vector<int> res;

        for(int i=0;i<nums.size();i++){
            if(mp.count(nums[i]) == 0){     //如果mp中不存在该数
                mp[nums[i]] = 1;
            }else{
                mp[nums[i]]++;
            }
        }

        //将mp里面的值放入到堆中
        for(map<int,int>::iterator it = mp.begin();it != mp.end();it++){
            q.push(node(it->first,it->second)); //使用first，second来访问
        }

        while(k--){
            res.push_back(q.top().val);
            q.pop();
        }

        return res;
    }
};

码后反思

1. 虽然我上面的代码用到了堆，但是堆的设计并不完美，我的堆的大小是N，那么取前k个元素的时间复杂度为$klogN$klogN；
2. 温习了STL的map的使用
3. 我看网友的题解，他们设计堆的大小为k，而且是小根堆。他们首先读入k个元素，之后的元素与小根堆堆顶进行比较，如果大于堆顶就移除堆顶，加入该元素，这样的时间复杂度为$Nlogk$Nlogk。运行结果和代码如下：
   
   好像时间还变长了？？？
   ????原因好像是最后的reverse()操作增加了用时，其实可以不用reverse，leetcode认为是无序的~删除reverse()之后还是60ms，感觉这个$Nlogk$Nlogk在这里没啥大用处，但是这个思想是很正确的，需要记住

   //如果不是出现在堆排序的题目里面，我很难想到要用堆排序
   //还有就是使用堆，真的可以吗？
   //首要要记录所有的数字出现的次数，时间复杂度为O(n)，使用map存储
   //数组不能为空，而且k是有效的
   struct node{
       int val;
       int cnt;
       node(int _val,int _cnt):val(_val),cnt(_cnt){}
       friend bool operator < (node a,node b){
           return a.cnt > b.cnt;
       }
   };
   
   class Solution {
   public:
       vector<int> topKFrequent(vector<int>& nums, int k) {
           map<int,int> mp;
           priority_queue<node> q;
           vector<int> res;
   
           for(int i=0;i<nums.size();i++){
               if(mp.count(nums[i]) == 0){     //如果mp中不存在该数
                   mp[nums[i]] = 1;
               }else{
                   mp[nums[i]]++;
               }
           }
   
           //将mp里面的值放入到堆中
           for(map<int,int>::iterator it = mp.begin();it != mp.end();it++){
               if(q.size()<k){ //如果当前堆的元素小于k，说明可以继续放
                   q.push(node(it->first,it->second)); //使用first，second来访问
               }else{  //当前堆的元素等于k了
                   if(it->second > q.top().cnt){
                       q.pop();
                       q.push(node(it->first,it->second)); //使用first，second来访问
                   }
               }
           }
   
           while(k--){
               res.push_back(q.top().val); //这里是逆序的，我们得反过来
               q.pop();
           }
           reverse(res.begin(),res.end());
           return res;
       }
   };