前 K 个高频元素
Top K Frequent Elements
本机进度仅保存在当前浏览器
题目描述
给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素，答案顺序任意，题目保证答案唯一。
示例：nums = [1, 1, 1, 2, 2, 3]，k = 2，输出 [1, 2]。
解题思路
- 第一步用哈希表统计频率；问题转化为"按频率取前 k 个"。
- 小顶堆维护 k 个最高频候选：堆满后新元素频率高于堆顶才替换，总代价 O(n log k)。
- 频率上界为 n，还可以做桶排序：频率作桶下标，倒序收集桶，得到 O(n) 解法。
参考实现
查看参考实现Python · 建议先自行作答
import heapq
from collections import Counter
def topKFrequent(nums, k):
count = Counter(nums)
# 大小为 k 的小顶堆，堆顶是当前第 k 高频
heap = []
for val, freq in count.items():
heapq.heappush(heap, (freq, val))
if len(heap) > k:
heapq.heappop(heap)
return [val for _, val in heap]