Top K 问题 题目描述 Top K 问题是指在一个包含 n 个元素的数据集中，找出前 K 个最大或最小的元素。例如，在搜索引擎中统计热门搜索词，或在海量日志中找出访问频率最高的前 K 个 IP 地址。这类问题通常要求高效处理大规模数据，且时间复杂度尽可能低。 解题思路 解决 Top K 问题需根据数据量、内存限制及对时间复杂度的要求选择不同策略。下面从简单到高效逐步分析常见解法。 方法一：全局排序（暴力法） 思路 ：直接对全部 n 个元素排序（如快速排序），然后取前 K 个元素。 时间复杂度 ： 排序需 O(n log n)，取前 K 个需 O(K)，总体 O(n log n)。 缺点 ： 当 n 极大时排序效率低，且可能无法全部载入内存。 适用场景 ：数据量较小且可一次性加载到内存中。 方法二：局部排序（冒泡/选择排序优化） 思路 ：仅排序出前 K 个元素，无需全局排序。 例如，使用选择排序或冒泡排序的变种，每轮找出一个最大值，执行 K 轮。 时间复杂度 ： 每轮需遍历 n 个元素，共 K 轮，为 O(nK)。 缺点 ： 当 K 接近 n 时退化为 O(n²)。 适用场景 ：K 远小于 n，且对效率要求不高。 方法三：堆（优先队列） 这是最常用的高效解法，分两种情况： 3.1 找前 K 个最小元素 思路 ：使用 最大堆 （Max-Heap）保存当前最小的 K 个元素。 步骤： a. 创建一个最大堆，容量为 K。 b. 遍历前 K 个元素直接加入堆。 c. 从第 K+1 个元素开始，若当前元素小于堆顶（即小于当前 K 个元素中的最大值），则替换堆顶并调整堆。 d. 遍历完成后，堆中即为前 K 个最小元素。 时间复杂度 ： 建堆 O(K)，调整堆 O(log K)，共调整 n-K 次，总体 O(n log K)。 空间复杂度 ：O(K)。 3.2 找前 K 个最大元素 思路 ：使用 最小堆 （Min-Heap）保存当前最大的 K 个元素。 步骤： a. 创建一个最小堆，容量为 K。 b. 遍历前 K 个元素直接加入堆。 c. 从第 K+1 个元素开始，若当前元素大于堆顶（即大于当前 K 个元素中的最小值），则替换堆顶并调整堆。 d. 遍历完成后，堆中即为前 K 个最大元素。 时间复杂度 ：同上，O(n log K)。 为什么堆是高效的？ 堆调整仅影响局部，无需全局排序，适合海量数据流（数据逐条输入，无需全部加载）。 方法四：快速选择算法（QuickSelect） 思路 ：基于快速排序的划分（Partition）操作。 步骤： a. 随机选取一个基准元素（pivot），将数组划分为左右两部分。 b. 若基准索引正好为 K，则左侧即为前 K 个最小元素（需注意顺序可能乱）。 c. 若基准索引大于 K，在左半部分递归；若小于 K，在右半部分递归。 时间复杂度 ： 平均 O(n)，最坏 O(n²)（但可通过随机化避免）。 缺点 ： 需要修改原数组，且不适用于数据流场景。 优化 ：结合 BFPRT 算法（中位数的中位数）确保最坏 O(n)，但实际工程中较少使用。 方法五：分治法（MapReduce 思路） 思路 ：适用于分布式系统或海量数据。 步骤： a. 将数据分片到多个机器，每台机器本地计算 Top K。 b. 汇总所有机器的局部 Top K，再全局计算最终 Top K。 优点 ： 通过并行处理降低单机压力。 总结与对比 | 方法 | 时间复杂度 | 空间复杂度 | 适用场景 | |--------------|------------------|------------|------------------------------| | 全局排序 | O(n log n) | O(n) | 数据量小，内存充足 | | 局部排序 | O(nK) | O(1) | K 非常小 | | 堆 | O(n log K) | O(K) | 海量数据流，内存有限 | | 快速选择 | O(n) 平均 | O(1) | 可修改原数组，无需保留完整顺序 | | 分治法 | 依赖并行度 | O(mK) | 分布式系统，数据极大 | 实际应用建议 面试中通常优先选择 堆解法 ，因其平衡了效率与通用性。 若数据可一次性加载且允许修改数组，可考虑 快速选择 。 遇到海量数据时，需结合数据特点（如是否重复多）选择桶排序或分治策略。