LeetCode 347：前 K 个高频元素 | 桶排序与哈希表的结合

LeetCode 347前 K 个高频元素 | 桶排序与哈希表的结合引言前 K 个高频元素Top K Frequent Elements是 LeetCode 第 347 题难度为 Medium。题目要求找出数组中出现频率最高的 K 个元素。这道题综合运用了哈希表和桶排序或者堆展示了如何结合多种数据结构来解决实际问题。这个问题有多种解法使用哈希表统计频率然后使用堆或排序来找到 Top K。桶排序方法是一种更巧妙的解决方案它利用了频率的范围特性将时间复杂度降低到 O(n)。本文将详细讲解各种解法并分析它们的优劣。问题分析题目描述给定一个整数数组 nums 和一个整数 K返回出现频率最高的 K 个元素。答案可以按任意顺序返回。例如输入 nums [1,1,1,2,2,3]K 2返回 [1, 2]因为 1 出现 3 次2 出现 2 次。又如输入 nums [1]K 1返回 [1]。问题特点这道题的核心挑战在于如何高效地找出出现频率最高的 K 个元素。如果使用简单的排序方法按频率排序后取前 K 个时间复杂度为 O(n log n)。如果使用堆可以在 O(n log k) 时间内解决。桶排序方法是一种更巧妙的解决方案。观察可知频率的最大值最多是数组长度 n因此我们可以创建 n 个桶将出现频率为 i 的元素放入第 i 个桶中。然后从后往前遍历桶找到非空的桶取出其中的元素直到达到 K 个。解决方案对比哈希表 堆import heapq from collections import Counter def topKFrequent_heap(nums, k): count Counter(nums) return heapq.nlargest(k, count.keys(), keycount.get)这种方法首先使用哈希表Counter统计每个元素的出现频率然后使用堆找出频率最高的 K 个元素。时间复杂度为 O(n k log n)空间复杂度为 O(n)。哈希表 桶排序def topKFrequent_bucket(nums, k): count Counter(nums) freq [[] for _ in range(len(nums) 1)] for num, freq_val in count.items(): freq[freq_val].append(num) result [] for i in range(len(nums), 0, -1): for num in freq[i]: result.append(num) if len(result) k: return result return result这种方法的核心思想是将频率作为桶的索引。freq[i] 存储所有出现频率为 i 的元素。从后往前遍历桶将元素取出直到达到 K 个。哈希表 快速排序思想def topKFrequent_quickselect(nums, k): count Counter(nums) unique list(count.keys()) def partition(left, right, pivot_idx): pivot_freq count[unique[pivot_idx]] unique[pivot_idx], unique[right] unique[right], unique[pivot_idx] store_idx left for i in range(left, right): if count[unique[i]] pivot_freq: unique[store_idx], unique[i] unique[i], unique[store_idx] store_idx 1 unique[right], unique[store_idx] unique[store_idx], unique[right] return store_idx left, right 0, len(unique) - 1 while left right: pivot_idx partition(left, right, (left right) // 2) if pivot_idx len(unique) - k: return unique[pivot_idx:] elif pivot_idx len(unique) - k: right pivot_idx - 1 else: left pivot_idx 1这种方法使用快速排序的思想快速选择算法在平均 O(n) 时间内找到 Top K 元素。但实现较复杂实际应用中不如堆方法常用。桶排序详解桶排序原理桶排序是一种分布式排序算法它将元素分散到多个桶中每个桶内部独立排序然后按顺序合并所有桶。对于前 K 个高频元素问题我们可以将桶的索引设为频率freq[i] 存储所有出现频率为 i 的元素。由于频率的范围是 1 到 n数组长度我们只需要 n1 个桶。遍历哈希表将每个元素放入对应频率的桶中。然后从后往前遍历桶从高频率到低频率收集 K 个元素即可。为什么桶排序适合这个问题桶排序适合这个问题的原因在于频率的取值范围是有限的。对于长度为 n 的数组任意元素的出现频率最多为 n。这意味着我们只需要 n1 个桶频率 0 到 n就能将所有元素按频率分类。而且由于我们需要的是最高的 K 个频率从最高频率开始收集自然就是按频率从高到低的顺序不需要额外的排序步骤。代码实现Python 实现from collections import Counter def topKFrequent(nums, k): count Counter(nums) freq [[] for _ in range(len(nums) 1)] for num, freq_val in count.items(): freq[freq_val].append(num) result [] for i in range(len(nums), 0, -1): for num in freq[i]: result.append(num) if len(result) k: return result return resultJava 实现public int[] topKFrequent(int[] nums, int k) { MapInteger, Integer count new HashMap(); for (int num : nums) { count.put(num, count.getOrDefault(num, 0) 1); } ListInteger[] freq new ArrayList[nums.length 1]; for (int i 0; i freq.length; i) { freq[i] new ArrayList(); } for (Map.EntryInteger, Integer entry : count.entrySet()) { freq[entry.getValue()].add(entry.getKey()); } int[] result new int[k]; int idx 0; for (int i nums.length; i 0 idx k; i--) { for (int num : freq[i]) { result[idx] num; if (idx k) { return result; } } } return result; }复杂度分析桶排序方法时间复杂度为 O(n)其中 n 是数组长度。哈希表构建需要 O(n)遍历哈希表并将元素放入桶需要 O(n)从后往前遍历桶收集结果最多需要 O(n)。空间复杂度为 O(n)用于存储哈希表和桶。堆方法时间复杂度为 O(n k log n)。哈希表构建需要 O(n)堆操作需要 O(k log n)如果使用堆维护 Top K或 O(n log n)如果对所有 n 个元素建堆。空间复杂度为 O(n)。快速选择方法平均时间复杂度为 O(n)最坏情况为 O(n²)。空间复杂度为 O(n)存储唯一元素。边界情况处理空数组当数组为空时哈希表为空桶也为空返回空列表。代码正确处理了这种情况。K 等于唯一元素数量当 K 等于数组中不同元素的数量时应该返回所有元素按频率降序排列。从后往前遍历桶会收集所有非空桶中的元素。所有元素出现频率相同当所有元素出现频率相同时如 [1, 2, 3, 4] 和 K 2结果可以是任意两个元素。代码会从前向后取元素。单个元素出现多次当只有一个元素但出现多次时如 [1, 1, 1, 1] 和 K 1返回 [1]。变种问题流数据中的 Top K如果数据是不断到来的流而不是静态数组可以使用堆来维护当前的 Top K。遇到新元素时更新堆并保持大小为 K。这种方法适用于实时系统。加权频率如果每个元素除了频率还有权重需要找出加权和中最高的 K 个元素可以修改比较函数来考虑权重。近似 Top K如果数据量非常大可以使用近似算法如 Count-Min Sketch 来估计频率然后在估计的基础上找出 Top K。这种方法适用于超大规模数据。测试用例def test_top_k_frequent(): assert topKFrequent([1, 1, 1, 2, 2, 3], 2) [1, 2] assert topKFrequent([1], 1) [1] assert set(topKFrequent([1, 2], 1)) {1, 2} assert set(topKFrequent([1, 1, 2, 2, 3], 2)) {1, 2} assert topKFrequent([1, 1, 1, 2, 2, 3], 3) [1, 2, 3] or set(topKFrequent([1, 1, 1, 2, 2, 3], 3)) {1, 2, 3} print(所有测试用例通过)实际应用场景Top K 问题在现实中有很多应用。在搜索引擎中需要返回最相关的 K 个搜索结果。在推荐系统中需要找出最可能被用户点击的 K 个物品。在社交网络中需要找出影响力最大的 K 个用户。在日志分析中需要找出访问量最高的 K 个页面。桶排序作为一种线性时间排序算法适用于数据分布均匀的场景。在 Top K 问题中桶排序利用了频率的有限范围实现了 O(n) 的时间复杂度是一种巧妙的问题解决方法。总结前 K 个高频元素问题展示了哈希表与其他数据结构结合的强大能力。哈希表用于统计频率桶排序或堆用于高效地找出 Top K。桶排序方法利用了频率的有限范围实现了线性时间复杂度的解决方案。在面试中可能会要求使用多种方法解决这个问题考察对不同数据结构的理解。希望通过本文的讲解读者能够掌握 Top K 问题的多种解法并理解何时应该选择哪种方法。