CS-Notes 剑指 Offer 题解：「最小的 K 个数」两种经典解法——大顶堆与快速选择

2026-09-04 13:37:24作者：瞿蔚英Wynne

本篇基于 CS-Notes 仓库中《剑指 Offer 题解》的 40. 最小的 K 个数展开，完整讲解“求数组中最小的 K 个数”这一高频面试题的两条技术路线：用大小为 K 的大顶堆维护候选集合（O(NlogK)），以及复用快速排序的 partition 切分实现快速选择（平均 O(N)）。读完后你能掌握每种解法的完整可运行 Java 代码、适用前提（是否允许修改原数组、数据规模是否海量），并能结合仓库内堆与排序的基础篇源码，理解大顶堆维护 TopK 和 partition 切分的底层机制。

问题背景与仓库定位

本题出自何海涛《剑指 Offer》，在仓库的剑指 Offer 题解 - 目录中被归入“栈队列堆”分类，与 41.1 数据流中的中位数、59. 滑动窗口的最大值等题并列——这提示我们该题的核心数据结构是堆。题目要求：给定一个数组，找出其中最小的 K 个数。例如从 {4, 5, 1, 6, 2, 7, 3, 8} 中找出 {1, 2, 3, 4}。

仓库原文给出了两种解法及其复杂度结论：

解法	时间复杂度	空间复杂度	关键前提
大小为 K 的最小堆（大顶堆实现）	O(NlogK) + O(K)	O(K)	特别适合海量数据，不要求修改原数组
快速选择	O(N) + O(1)	O(1)	只有当允许修改数组元素时才可以使用

下面逐一展开。

解法一：大小为 K 的大顶堆（TopK 模板）

核心思路：为什么必须用“大顶堆”

原文明确指出一个常见的认知陷阱：

应该使用大顶堆来维护最小堆，而不能直接创建一个小顶堆并设置一个大小，企图让小顶堆中的元素都是最小元素。

原因在于堆顶的语义：

小顶堆的堆顶是堆中最小元素。若往小顶堆里不断加元素、超出 K 个时弹出堆顶，被弹出的是当前最小的那个——恰好把我们想要留下的元素删掉了；
大顶堆的堆顶是堆中最大元素。维护过程是：每加入一个元素，若堆大小超过 K，就弹出堆顶，即踢掉当前堆中最大的那个。这样留在堆里的 K 个元素，一定都不超过任何被踢掉的元素，最终恰好是全局最小的 K 个。

这正是 TopK 问题的标准套路。仓库的 Leetcode 题解 - 排序对同一模型有更完整的表述：不断往大顶堆中插入新元素，当堆中元素数量大于 k 时移除堆顶（当前最大元素），剩下的就是最小的 K 个；插入与移除堆顶的时间复杂度均为 log₂N。

完整代码

Java 的 PriorityQueue 实现了堆的能力，默认是小顶堆；初始化时传入 Lambda 表达式 (o1, o2) -> o2 - o1 即可实现大顶堆，其它语言也有类似的堆数据结构。

public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {
    if (k > nums.length || k <= 0)
        return new ArrayList<>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
    for (int num : nums) {
        maxHeap.add(num);
        if (maxHeap.size() > k)
            maxHeap.poll();
    }
    return new ArrayList<>(maxHeap);
}

代码要点逐行说明：

边界判断：k > nums.length || k <= 0 时直接返回空列表，覆盖 K 越界与非法 K；
比较器 (o1, o2) -> o2 - o1：让大值排前面，使 PriorityQueue 成为大顶堆；
add + 条件 poll：先无条件入堆，堆一旦超过 K 个就弹出堆顶（堆内最大值）。注意这里是“先加后弹”而非“弹前比较”，因此堆在中间过程中可能瞬时达到 K+1 个元素，但最终恒定不超 K；
收尾：new ArrayList<>(maxHeap) 取出剩余元素。注意返回结果是大顶堆的底层数组顺序，并不保证有序；若题目要求升序输出，需要再对 K 个元素做一次 O(KlogK) 的小规模排序。

复杂度与适用场景

每个元素入堆/出堆代价 O(logK)，共 N 个元素，故时间复杂度 O(NlogK)；堆最多容纳 K 个元素，空间 O(K)；
原文特别标注它特别适合处理海量数据：因为堆中只需保留 K 个候选值，数据可以流式（一条一条）读入，无需把全部 N 个数据都驻留在内存中。仓库中同一套“大顶堆技巧”也用于 41.1 数据流中的中位数（用 new PriorityQueue<>((o1, o2) -> o2 - o1) 建左半大顶堆存储较小的一半元素），可见这是该仓库处理流式数据的一贯手法。

解法二：快速选择（Quickselect）

原理：借用快速排序的 partition

快速排序的 partition() 方法执行后，会返回一个整数 j，使得 a[l..j-1] 都小于等于 a[j]，且 a[j+1..h] 都大于等于 a[j]——此时 a[j] 恰好是数组的第 j 大（0 起算第 j+1 小）元素。这个性质正是快速选择的立足点：找最小的 K 个数，等价于找到第 K 小的元素（下标 k-1）并把它切分到正确位置，此时前 K 个位置自然就是答案。

上图（取自仓库算法 - 排序快速排序“切分”一节）展示了 partition 的双指针扫描与交换过程，与快速选择中使用的 partition 完全一致。

完整代码

public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {
    ArrayList<Integer> ret = new ArrayList<>();
    if (k > nums.length || k <= 0)
        return ret;
    findKthSmallest(nums, k - 1);
    /* findKthSmallest 会改变数组，使得前 k 个数都是最小的 k 个数 */
    for (int i = 0; i < k; i++)
        ret.add(nums[i]);
    return ret;
}

public void findKthSmallest(int[] nums, int k) {
    int l = 0, h = nums.length - 1;
    while (l < h) {
        int j = partition(nums, l, h);
        if (j == k)
            break;
        if (j > k)
            h = j - 1;
        else
            l = j + 1;
    }
}

private int partition(int[] nums, int l, int h) {
    int p = nums[l];     /* 切分元素 */
    int i = l, j = h + 1;
    while (true) {
        while (i != h && nums[++i] < p) ;
        while (j != l && nums[--j] > p) ;
        if (i >= j)
            break;
        swap(nums, i, j);
    }
    swap(nums, l, j);
    return j;
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

关键实现细节：

递归变迭代：findKthSmallest 用 while (l < h) 循环代替快速排序的递归。每轮 partition 后只收缩到 j 所在的一侧继续切分，舍弃的另一侧完全不再处理——这是它只找“第 K 小”而非整体排序的根本原因；
partition 的指针约定：取 nums[l] 为切分元素 p；左指针 i 从左向右跳过小于 p 的元素，右指针 j 从右向左跳过大于 p 的元素，二者相遇前交换逆序对；最后把 p 换到下标 j 处并返回 j。仓库算法 - 排序中快速排序的 partition（基于泛型 Comparable 的版本）与本实现是同构的，可对照阅读；
原数组被破坏：如代码注释所述，findKthSmallest 执行后前 k 个数即最小的 k 个数，但整个数组其余部分的相对顺序已打乱。因此原文强调“只有当允许修改数组元素时才可以使用”；
最坏情形提示：partition 固定取左端元素 nums[l] 作为切分元素，若输入接近有序，切分会严重失衡。仓库 Leetcode 题解 - 排序在讲解同一算法时明确提醒：“需要先打乱数组，否则最坏情况下时间复杂度为 O(N²)”；算法 - 排序中 QuickSort.sort 开头调用 shuffle(nums) 也是同一目的。随机化之后，期望时间复杂度回到线性。

为什么平均是 O(N)

从源码结构看，findKthSmallest 每轮 partition 只在一个长度为前一轮一半（期望意义下）的子区间上工作。假设每轮恰好将区间对半切分，比较总次数为 N + N/2 + N/4 + …，这个几何级数小于 2N，因此算法整体是线性级别的——这正是原文给出“O(N) + O(1)”的推导依据，与仓库算法 - 排序 “基于切分的快速选择算法”一节的分析一致。

两种解法对比与选型建议

维度	大顶堆（解法一）	快速选择（解法二）
时间复杂度	O(NlogK)（稳定）	平均 O(N)，最坏 O(N²)（未随机化时）
空间复杂度	O(K)	O(1)
是否修改原数组	否	是
是否支持流式/海量数据	是，堆中仅驻留 K 个元素	否，需要整段数组参与 partition
典型应用	TopK、数据流、外部排序归并阶段	一次性给定的整块数组求 K 最小/第 K 小

选型上的经验规律：

K 远小于 N，或数据以流的形式到来（无法全部载入内存）时，优先大顶堆；
数据一次性可得且允许原地修改、追求常数最小时，优先快速选择；
若数据量很小，直接全排序 O(NlogN) 实现最简单，也是可接受的基线方案——仓库 Leetcode 题解 - 排序给出的 Arrays.sort 基线即属此类。