Top K 问题的高效解法与比较 题目描述 给定一个无序数组和整数 K，要求找出数组中前 K 个最大（或最小）的元素。例如，输入 [3, 2, 1, 5, 6, 4] 且 K=2 ，返回前 2 个最大的元素 [6, 5] 。该问题需分析不同数据规模下的最优解法。 解题步骤 暴力排序法（直接但低效） 步骤： 对数组整体排序（如降序）。 取前 K 个元素作为结果。 时间复杂度：O(n log n)，适用于 K 接近 n 的情况。 缺点：当 K < < n 时（例如 K=100, n=1 亿），排序整个数组浪费计算量。 基于堆的优化解法（适用于海量数据） 核心思想 ：维护一个大小为 K 的堆，避免全局排序。 找前 K 个最大元素 ： 用 最小堆 （堆顶为最小元素）存储当前最大的 K 个数。 遍历数组： 若堆大小 < K，直接插入元素。 若堆已满且当前元素 > 堆顶，弹出堆顶后插入新元素。 遍历完成后，堆中即为前 K 个最大元素。 时间复杂度 ：O(n log K)，空间复杂度 O(K)。 为什么用最小堆 ：堆顶是当前 K 个数中的最小值，遇到更大的数时需更新堆。 示例 （数组 [3,2,1,5,6,4] , K=2）： 初始化最小堆 [] 。 插入 3 → [3] ；插入 2 → [2,3] （堆顶为 2）。 遇到 1（1 < 堆顶 2，跳过）；遇到 5（5 > 2）→ 弹出 2，插入 5 → [3,5] 。 遇到 6（6 > 堆顶 3）→ 弹出 3，插入 6 → [5,6] ；遇到 4（4 < 堆顶 5，跳过）。 结果： [5,6] 。 快速选择算法（平均 O(n)，但需处理边界） 核心思想 ：借鉴快速排序的划分（Partition），每次确定一个元素的最终位置。 步骤 ： 随机选取基准值（pivot），将数组划分为左右两部分。 若基准值位置正好是第 K 大（或第 n-K 小）元素，则其左侧（或右侧）即为前 K 个最大（或最小）元素。 否则递归处理目标所在的分区。 时间复杂度 ：平均 O(n)，最坏 O(n²)（可通过随机化避免）。 适用场景 ：适合数据可全部加载到内存，且不要求结果有序的情况。 不同场景下的选择建议 K 接近 n：直接排序（代码简单）。 K < < n 且数据量极大：堆解法（节省内存和计算）。 对时间复杂度敏感且数据可随机访问：快速选择。 数据流场景（无法一次性加载）：只能使用堆。 总结 Top K 问题的核心是 根据 K 与 n 的关系选择策略 。堆解法通用性强，快速选择平均效率高但需注意最坏情况，排序法在 K 较大时反而更直接。实际面试中需结合数据特征和约束条件展开分析。