LeetCode 前 K 个高频元素题解
题目描述
给你一个整数数组nums和一个整数k，请你返回其中出现频率前k高的元素。
示例：
输入：nums = [1,1,1,2,2,3],k = 2
输出：[1,2]
解题思路
方法：哈希表 + 堆
思路：
- 使用哈希表来统计每个元素出现的频率。
- 使用一个小顶堆来维护前 k 个高频元素。
- 遍历哈希表，将元素和其频率加入堆中，如果堆的大小超过 k，弹出堆顶元素。
- 最后将堆中的元素转换为列表返回。
复杂度分析：
- 时间复杂度：O(n log k)，其中 n 是数组的长度。遍历数组的时间复杂度是 O(n)，堆操作的时间复杂度是 O(n log k)。
- 空间复杂度：O(n)，需要额外的空间来存储哈希表和堆。
代码实现
方法：哈希表 + 堆
import heapq from collections import defaultdict # 前 K 个高频元素（哈希表 + 堆） def top_k_frequent(nums, k): # 统计每个元素出现的频率 count = defaultdict(int) for num in nums: count[num] += 1 # 使用小顶堆来维护前 k 个高频元素 heap = [] for num, freq in count.items(): heapq.heappush(heap, (freq, num)) if len(heap) > k: heapq.heappop(heap) # 将堆中的元素转换为列表 result = [] while heap: result.append(heapq.heappop(heap)[1]) # 反转列表，使频率高的元素在前 return result[::-1] # 测试 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()测试用例
测试用例 1：基本情况
输入：nums = [1,1,1,2,2,3],k = 2
输出：[1,2]
总结
前 K 个高频元素是一个经典的哈希表问题，它可以通过哈希表和堆来高效地解决。
哈希表 + 堆法的核心思想是：使用哈希表统计每个元素出现的频率，然后使用小顶堆来维护前 k 个高频元素。
掌握哈希表和堆的使用方法，对于解决类似的问题非常重要。
