给定一个未排序数组，如何输出第K大的数字？｜京东算法面经解析

60 秒回答模板

最直接方法是排序后取下标 n-K，时间 O(n log n)。如果数据流式或 K 很小，可以维护大小为 K 的小顶堆，堆顶就是当前第 K 大，时间 O(n log K)。如果追求平均线性复杂度，可以用 Quickselect：每次随机选 pivot 做 partition，把比 pivot 大的放一边，根据 pivot 排名决定递归哪一侧，平均 O(n)，最坏 O(n^2)，可用随机 pivot 降低风险。

考点 排序最简单

难度 真实面经题

回答目标 讲清方法、取舍和追问

深入解析

排序基线

排序是最容易写对的方案，先把数组升序或降序排好，再按 K 找位置。它适合数据量不大或开发时间紧的场景，但没有利用只需要第 K 大这个信息，复杂度较高。

小顶堆方案

维护一个大小为 K 的小顶堆，遍历每个元素；堆未满就加入，堆满后如果当前元素大于堆顶，就替换堆顶。遍历结束后堆顶就是第 K 大，适合 K 远小于 n 或数据流场景。

Quickselect 思路

Quickselect 借用快排 partition。每轮把 pivot 放到最终排名位置，然后判断第 K 大目标在 pivot 左边还是右边，只递归一侧，因此平均只扫描线性规模。

处理重复和边界

要明确 K 从 1 开始还是从 0 开始，K 是否越界，以及重复元素按值排名还是按位置排名。partition 时可以用三路划分减少大量重复值导致的退化。

复杂度取舍

排序稳定简单但 O(n log n)，堆是 O(n log K)，Quickselect 平均 O(n) 但最坏 O(n^2)。生产实现中常用随机 pivot 或 median-of-three 提升稳定性。

javascript

Quickselect 查找第 K 大

function findKthLargest(nums, k) {
  if (k < 1 || k > nums.length) throw new Error('invalid k');
  const target = k - 1;
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const pivotIndex = partitionDesc(nums, left, right);
    if (pivotIndex === target) return nums[pivotIndex];
    if (pivotIndex < target) left = pivotIndex + 1;
    else right = pivotIndex - 1;
  }
}

function partitionDesc(nums, left, right) {
  const pivot = nums[right];
  let store = left;
  for (let i = left; i < right; i += 1) {
    if (nums[i] > pivot) {
      [nums[store], nums[i]] = [nums[i], nums[store]];
      store += 1;
    }
  }
  [nums[store], nums[right]] = [nums[right], nums[store]];
  return store;
}

这里按降序 partition，因此第 K 大的目标下标是 `k - 1`。
生产实现应使用随机 pivot 或三路划分，降低有序数组和大量重复值的退化风险。

易错点

不要把第 K 大和第 K 小的下标换错，升序数组里第 K 大是 n-K。
不要忽略 K 越界，K 小于 1 或大于数组长度都应处理。
不要默认 Quickselect 一定 O(n)，它是平均 O(n)，最坏会退化。
不要用大顶堆保留全部元素，那会变成更高成本的排序变体。

面试官追问

为什么找第 K 大用小顶堆？

堆中保留当前最大的 K 个数，堆顶是这 K 个数里最小的，也就是遍历到当前为止的第 K 大候选。

Quickselect 最坏情况是什么？

如果每次 pivot 都极端偏斜，划分只减少一个元素，最坏会退化到 O(n^2)。随机 pivot 可以显著降低概率。

海量数据不能全放内存怎么办？

可以流式维护大小为 K 的小顶堆；如果数据分布在多机上，每台机器先保留局部 TopK，再合并这些候选求全局第 K 大。