LeetCode 前K个高频元素题解
题目描述
给定一个数组，找到前 k 个高频元素。
示例：
输入：nums = [1,1,1,2,2,3],k = 2
输出：[1,2]
解题思路
方法：堆
思路：
- 使用哈希表统计每个元素出现的次数。
- 使用最小堆维护前 k 个高频元素。
- 遍历哈希表，将每个元素加入堆中。
- 如果堆的大小超过 k，则弹出堆顶元素。
- 最后堆中的元素就是前 k 个高频元素。
复杂度分析
- 时间复杂度：O(n log k)
- 空间复杂度：O(n)
代码实现
import heapq from collections import Counter def top_k_frequent(nums, k): count = Counter(nums) heap = [] for num, freq in count.items(): heapq.heappush(heap, (freq, num)) if len(heap) > k: heapq.heappop(heap) return [num for freq, num in heap] # 测试 def test_top_k_frequent(): nums = [1, 1, 1, 2, 2, 3] k = 2 print(top_k_frequent(nums, k)) # 输出：[1, 2] if __name__ == "__main__": test_top_k_frequent()总结
前K个高频元素是堆的典型应用，通过维护一个大小为 k 的堆来找出前 k 个高频元素。
