Leetcode347. 前 K 个高频元素 Top K Frequent Elements - Python 以小顶堆实现

import heapq
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        map_ = {}    #用字典遍历整个nums，存储各元素出现频率
        for i in range(0,len(nums)):
            map_[nums[i]] = map_.get(nums[i],0) + 1
        pri_q = []
        #用小顶堆遍历整个map，不断将频率表按照频率从小到大排列
        for key, freq in map_.items():
            heapq.heappush(pri_q,(freq,key))
            if len(pri_q) > k:  #只维护前k个元素
                heapq.heappop(pri_q) #弹出的是最小的频率次数，高频数字会被保留
        result= [0]*k
        # for i in range(0,len(pri_q)):
        #     result[i] = pri_q[i][1] #因题目要求可以按任意顺序返回结果，所以可以不按频率高低返回
        for i in range(k-1,-1,-1):
            result[i] = heapq.heappop(pri_q)[1] #练习一下按照频率高低返回
        return result

思路：

此题需要掌握了解小顶堆，大顶堆以及优先队列的工作原理。【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆_哔哩哔哩_bilibili

其次需要注意整个流程：

先将各个数字频率加入哈希表；

用小顶堆而不是大顶堆建堆遍历哈希表，因为小顶堆每次弹出的是最小频率，将高频率保存了下来；

只需维护前k个元素即可；