2022·42 十万数找最小 10 个：全排序到大根堆门槛过滤

本文属于「从暴力解到最优解」专题的第二组，但和前面「真不用优化」的题不同——它是一个反例。总纲判断一道题要不要优化的简单方法是看题面有没有出现「尽可能高效」四个字，这道题确实没有，所以它被归进了第二组的表格。但它的题干里另有一句「要求平均情况下的比较次数尽可能少」——换了个说法，说的是同一件事。只数关键词是不够的，题面的其它措辞、甚至给定的数据规模本身，都可能悄悄夹带最优性要求。这道题就是练这份警觉的最佳材料。

题目

现有 n（n > 100000）个数保存在一维数组 M 中，需要查找 M 中最小的 10 个数，请回答下列问题：

(1) 设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简单描述其算法思想，不需要程序实现。 (2) 说明你所设计的算法平均情况下的时间复杂度和空间复杂度。

总分 10 分（正确性 6 分、最优性 4 分）。优化要求就藏在 (1) 问那句「比较次数尽可能少」里——它没有说「时间复杂度尽可能低」，也没有说「尽可能高效」，但「比较次数」正是这道题的计价单位，效果完全一样。另外要注意，(1) 问明确写了「不需要程序实现」，只要把算法思想讲清楚即可；下文仍然给出两版 C 代码，是为了让暴力解和最优解的差别看得更直白，考场上并不需要真的写出来。

第一步：把暴力解写对

n 远大于 10，考场上最直接的反应通常是：把 n 个数全排序，排完前 10 个就是答案。

#include <stdlib.h>

int cmpInt(const void *a, const void *b) { return *(int *)a - *(int *)b; }

// 全排序后取前 10 个：结果一定正确，但排序本身要付出 O(n log n) 次比较
void findMinKBruteForce(int M[], int n, int result[]) {
    int *copy = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) copy[i] = M[i];
    qsort(copy, n, sizeof(int), cmpInt);      // 排序算法内部比较次数 O(n log n)
    for (int i = 0; i < 10; i++) result[i] = copy[i];
    free(copy);
}

复杂度：排序占主导，比较次数 $O(n\log n)$；额外拷贝一份数组，空间 $O(n)$（若原地排序可降到 $O(1)$）。

它值多少分

408 算法设计题通常按正确性/最优性两个维度判分（详见总纲），但这道题要格外小心：它把「最优」直接写进了 (1) 问的设问里，于是最优性的占比是全专题最高的一档——10 分里有 4 分挂在「用没用上能让比较次数最少的方法」上，而别的题通常只有 1~3 分。

• 结果本身没有问题：全排序一定能找出正确的最小 10 个数，这一点不会错。
• (1) 问 7 分里，3 分的正确性主分照拿：能正确选出最小 10 个数、说清留下的就是这 10 个，这一档与方法无关。
• 但 (1) 问那 4 分最优性拿不到：全排序不满足「比较次数尽可能少」，按不达最优处理。你说得再清楚，只要设计思想不是「用一种能让比较次数逼近 n 的方法」，这 4 分就落不到手里。
• (2) 问 3 分不受牵连：复杂度那一问看的是「写出来的复杂度与你自己的算法是否相符」，不是「是否等于 $O(n)$」。全排序照实写 $O(n\log n)$、额外空间照实写，一样给分——最优性的差距已经在 (1) 问扣过，不重复扣。

这道题和其它「暴力解拿正确性分、丢最优性分」的真题不太一样：别的题最优性只占 1~3 分，暴力解丢掉它无关痛痒；这道题最优性占了 4 分，全排序交上去是 6/10——正确性主分仍在手，但丢掉的那 4 分是实打实的。这也是为什么它被专题选作反例——看着像"随便一个正确算法就够了"的题，设问本身问的其实就是"怎样让比较次数最少"。

还有一条稍微体面一点的暴力路线：简单选择排序做 10 趟，每趟从剩余元素里选出最小的放到前面，比较次数约 $10n$。它的常数比全排序小、更贴近"直接奔着 10 个数去"的直觉，判分上也温和一些——方向对，最优性那档里"用定容结构只留最小 k 个"的 2 分能拿到 1 分，合计 7/10，比全排序高一档。可见暴力解之间也有优劣之分：全排序连"够不着最优"都不体面，选择排序至少是朝着正确方向迈了一步、只是常数因子不够好。

暴力解的浪费在哪

用总纲的三个问题审一遍全排序：

有没有放着性质不用？——有，而且是最大的浪费。我们要的只是最小的 10 个数，n 却有十万乃至更多。全排序把这 n 个数从头到尾都排出精确的相对顺序，但题目只要前 10 名，后面 99990 个数之间谁大谁小根本不关心。排序做的事情比题目要求的多太多了——你只想知道谁进前 10，它却把全员的名次都算了出来。

换个角度看：全排序里每次比较，参与的两个数都有可能是"注定进不了前 10"的两个大数——这种比较对最终答案毫无贡献，纯属陪跑。

智慧化改造：大小为 10 的大根堆门槛过滤

浪费找到了：不需要知道后 99990 个数的相对顺序，只需要一个能快速判断"新数能不能挤进前 10"的机制。

标准答案是维护一个大小为 10 的大根堆——注意，是大根堆，不是更符合直觉的小根堆：

1. 用 M 的前 10 个元素建一个大根堆，堆顶 top 是这 10 个数里最大的；
2. 对剩余 n − 10 个元素 v，先与堆顶比较 1 次：若 v ≥ top，v 不可能进前 10，直接跳过；否则用 v 替换堆顶，向下调整堆（$\lceil {\log }_{2}10\rceil \approx 4$ 层，约 7 次比较）；
3. 遍历完成，堆里就是最小的 10 个数。

反直觉的地方在于大根堆的堆顶恰好是当前 top-10 中最大的那个，天然就是一道"门槛"：新数只要不比门槛小，就注定进不了前 10，1 次比较即可判掉。n 巨大、k=10 很小，新数能打破门槛、挤进前 10 的概率极低，所以绝大多数元素只经历这 1 次比较就被淘汰，整体期望比较次数

$$10\times {\log }_{2}10+\sum _{i=11}^n(1+\frac{10}{i}\cdot {\log }_{2}10)\approx n+O(\log n)$$

量级是 $O(n)$，常数因子接近 1——这正是"比较次数尽可能少"这句话真正想要的东西。

#define K 10

// 大小为 K 的大根堆下沉调整
void siftDown(int heap[], int i, int size) {
    while (1) {
        int largest = i, left = 2 * i + 1, right = 2 * i + 2;
        if (left < size && heap[left] > heap[largest]) largest = left;
        if (right < size && heap[right] > heap[largest]) largest = right;
        if (largest == i) break;
        int tmp = heap[i]; heap[i] = heap[largest]; heap[largest] = tmp;
        i = largest;
    }
}

// 找出 M 中最小的 K 个数，结果放进 heap[0..K-1]（堆结构，未必有序）
void findMinKHeap(int M[], int n, int heap[]) {
    for (int i = 0; i < K; i++) heap[i] = M[i];        // 前 K 个建堆
    for (int i = K / 2 - 1; i >= 0; i--) siftDown(heap, i, K);

    for (int i = K; i < n; i++) {
        if (M[i] < heap[0]) {          // 门槛比较：1 次
            heap[0] = M[i];            // 替换堆顶
            siftDown(heap, 0, K);      // 向下调整
        }
        // 否则 M[i] >= 堆顶，直接跳过，这一轮只花了 1 次比较
    }
}

从暴力解升级过来，两个反直觉点务必记牢：

• 大根堆不是小根堆：找最小的 k 个，第一反应通常是"小根堆"，但小根堆的堆顶是当前最小值，没法 1 次比较判断"新元素是否比现有 top-k 都大"。只有大根堆的堆顶（top-k 里的最大者）才能当门槛用。
• 门槛比较是"1 次决定去留"：不是每个新元素都要走"替换 + 下沉"的完整流程，绝大多数元素在门槛比较那一步就出局了，这正是常数因子小的来源。

复杂度：时间 $O(n\log k)=O(n)$（k = 10 是常数）；空间 $O(k)=O(1)$，除入参 M 外只用了大小为 10 的堆数组，与 n 无关。这就是标准答案，(1)(2) 两问的分都能拿到。

两版对照跑一遍

演示数组缩小成十几个数、k 取 4（真题里 k = 10，这里改小只是为了让可视化步骤看得清楚，机制完全一样）。先看全排序版——注意它把整个数组都排出了顺序：

加载可视化中...

再看大根堆门槛版——注意大多数元素只经历了 1 次门槛比较，堆的下沉调整只在少数几次替换时才发生：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应；两版跑完得到的最小 k 个数集合完全一致，只是花的比较次数天差地别。

等价方法与升级空间

• 简单选择排序 10 趟：每趟 n − 1 次比较，共约 10n 次，常数比堆法大近 10 倍。方向是对的（确实在往"只关心前 10"上靠），判分上它能在最优性那档里拿到部分分，而不是像全排序那样整档落空——同样是暴力解，离最优的距离不一样，判分也不一样。
• 快速选择（quickselect）：平均 $O(n)$，量级上已经够了，但常数大、最坏情况 $O(n^2)$，还需要修改原数组。解析认为思想正确但不是本题最优选择，只给部分分——这是「方法等价但不是当前题目要的那个最优」的典型例子。
• 小根堆的常见误区：把"找最小 k 个"直觉套成"用小根堆"，会发现堆顶（当前最小值）根本没法充当"新元素能不能进前 k"的判断依据，这个误区在设计思想那一问按思路错处理，务必记住大根堆才是标准答案。

下一步

• 在 OJ 上把两版代码都提交跑一遍：ds-2022-42 Top-K 最小值
• 回到题库看这道题的完整解析与错因：真题库 · 数据结构

相关真题（7题）

2024Q92分2022Q4210分2021Q112分2020Q92分2015Q102分2011Q112分2009Q92分