leetcode 347 数组中前k个高频元素

解题思路：一个map,一个heap，和一个存放结果的列表list

1.map存储数组中元素和元素出现的频数

2.heap用来生成并维护一个具有k个元素的小顶堆，当元素个数超过k时，将堆顶元素弹出，最后留在堆里的元素即为最终的结果，存放在列表中

import heapq
 
class Solution:
    def top_k_freq(self, nums, k):
 
        #map用于存放数组中的元素及其出现的频数，分别用key，value存储
        map_freq = {}
 
        #小根堆，维持k个元素的小根堆,将剩余的元素输入并做调整后输出，最后留在小根堆里的元素逆序排                
        #列就是前k个高频元素
        heap = []
 
        for i in range(len(nums)):
            map_freq[nums[i]] = map_freq.get(nums[i], 0) + 1
 
        for key, value in map_freq.items():
            heapq.heappush(heap, (value, key))
            
            #维持k个元素的小根堆,若元素个数超过k个，就将堆顶元素弹出
            if len(heap) > k:
                heapq.heappop(heap)
 
 
        res = [0] * k
 
        for i in range(k-1, -1, -1):
            res[i] = heapq.heappop(heap)[1]
 
        return res
 
s = Solution()
res = s.top_k_freq(nums=[1,1,1,2,2,3], k=2)
print(res)