本文主要是介绍【hot100篇-python刷题记录】【前 K 个高频元素】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
R6-堆
印象题
法1：哈希表+排序
思路：
用哈希表记录吗每个数出现的次数，按照value值排序，输出倒数k个即可，但这样的话，需要根据values找keys，需要增加一遍遍历哈希表。
想到一个改进，直接用collections.Counter()，但这样的话，怎么输出又不太会处理，还是用第一种方法吧。
class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:dict=defaultdict(int)ret=[]for num in nums:dict[num]+=1final=sorted(dict.keys(),key= lambda x:dict[x],reverse=True)for i in range(k):ret.append(final[i])return ret
ps:靠，没用堆的知识
法2：最小堆维护k高
最大堆求topk小，最小堆求 topk 大
所以这里使用最小堆的知识。
import heapq
class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:#使用字典统计出现频率：dict=defaultdict(int)for num in nums:dict[num]+=1#最小堆，用于维护出现频率最高的k个数字#如果有数字比根节点还大的话，就需要重构该最小堆树minHeap=[]for num,fre in dict.items():#堆内元素不足k个--堆未满，直接添加if (len(minHeap)<k):heapq.heappush(minHeap,(fre,num))#堆满，且当前高于根节点，重建elif fre>minHeap[0][0]:heapq.heappushpop(minHeap,(fre,num))#最后，从小顶堆中提取前k个频率最高的元素ret=[num for fre,num in minHeap] return ret
ps:
字典的使用
dict.keys()
dict.values()
dict.items()堆的函数使用
这篇关于【hot100篇-python刷题记录】【前 K 个高频元素】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
