优先队列-小根堆留坑

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

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

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

提示：

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

class Solution {
public:class myComparison{public:bool operator()(const pair<int,int>&lhs,const pair<int,int>&rhs){return lhs.second>rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {//定义无序键值对unordered_map<int,int>map;for(int i=0;i<nums.size();i++){map[nums[i]]++;}//定义一个小顶堆,存储前k个频率最小的元素priority_queue<pair<int,int>,vector<pair<int,int>>,myComparison>pri_que;//扫描元素for(unordered_map<int,int>::iterator it= map.begin();it!=map.end();it++){pri_que.push(*it);if(pri_que.size()>k){pri_que.pop();//将最小元素弹出}}//找出频率最大的前k个元素vector<int>res(k);for(int i=k-1;i>=0;i--){res[i]=pri_que.top().first;pri_que.pop();}return res;}
};

import heapq   #维护小根堆的特性
class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:#定义字典来存放键和值map_={}for i in range(len(nums)):map_[nums[i]]=map_.get(nums[i],0)+1#以列表的形式定义小根堆pei_que=[]for key,fre in map_.items():heapq.heappush(pei_que,(fre,key))if len(pei_que)>k:heapq.heappop(pei_que)result=[0]*kfor i in range(k-1,-1,-1):result[i]=heapq.heappop(pei_que)[1]return result

单纯为了记录学习使用，无其他用途。