leetcode 347 前 K 个高频元素

Problem: 347. 前 K 个高频元素

思路

遍历容器，储存到map中，之后遍历map，维护k个小根堆，然后存储到堆中最后存储到结果集中

解题方法

1.手动实现operator运算来实现小根堆，之后再定义优先队列priotity的时候，需要的是三个参数，分别为堆中存储的数据类型，用什么容器来存储堆中的元素

2.统计元素的出现频率的时候，对于unordered_map来说，会自动有一个操作就是如果map中没有key的时候就会自动插入进去，如果有的话，就是堆value++操作

3.为什么在这里要使用小根堆？

因为如果使用大根堆的话，对于priority来说其中pop（）方法，弹出的就是二叉树的顶部，使用大根堆每次就是弹出的最大值，所以留下来的k个元素其实最小的k个，题目中要求的是最大的k个

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

class Solution {
public:
    // 自定义一个小顶堆
    class myCompartion{
        public:
            bool operator()(const pair<int,int>& Lval,const pair<int,int>& Rval){
                return Lval.second > Rval.second;
            }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 统计元素出现的频率
        unordered_map<int,int> un_map;
        for(int i=0;i<nums.size();i++){
            un_map[nums[i]]++;
        }
        // 定义小根堆
        // 第一个参数为优先队列中元素的类型，第二个参数为存储元素的容器
        priority_queue<pair<int,int>,vector<pair<int,int>>,myCompartion> pri_queue;
        // 遍历map存到小根堆中,这里是只维护k个元素的小根堆
        for(unordered_map<int,int>::iterator it=un_map.begin();it!=un_map.end();it++){
            pri_queue.push(*it);
            if(pri_queue.size() > k) pri_queue.pop();
        }
        vector<int> result(k);
        // 
        for(int i=0;i<k;i++){
            result[k-i-1]=pri_queue.top().first;
            pri_queue.pop();
        }
        // reverse(result.begin(),result.end());
        return result;
    }
};

通过