面试题40：最小的k个数

从“只要前k名，为什么给所有人排座次”开始

先预测：在4、5、1、6、2、7、3、8中找“最小的k个数”，k为4。完整排序当然能得到1、2、3、4，但题目只关心分界线：只要确认某个位置是第4小，且它左边恰有另外3个不更大的元素，前4个位置就构成答案集合，内部谁先谁后并不重要。

作者给出两条适用于不同约束的路线。解法一复用上一题的Partition，在完整可写数组上做；解法二把当前最小的k项保存在降序multiset里，可逐个读取数据且不修改输入。

解法一：Partition定位k减一

零基数组中，第k小元素的目标下标是k减一。Partition返回index后，作者按index与k减一的关系缩小start或end，直到二者相等。此时形成，复制input前k项即可。

void GetLeastNumbers_Solution1(
    int* input, int n, int* output, int k) {
    if (input == nullptr ||
        output == nullptr ||
        k > n ||
        n <= 0 ||
        k <= 0) {
        return;
    }
 
    int start = 0;
    int end = n - 1;
    int index = Partition(
        input, n, start, end);
 
    while (index != k - 1) {
        if (index > k - 1) {
            end = index - 1;
        } else {
            start = index + 1;
        }
        index = Partition(
            input, n, start, end);
    }
 
    for (int i = 0; i < k; ++i) {
        output[i] = input[i];
    }
}

正确性来自Partition不变量：主元落位后，左侧值都小于主元。若index大于目标，只需在左段继续；若index小于目标，只需在右段继续。index等于k减一时，任何后段元素都不会小于前k项中的边界元素，因此前k项作为多重集合正好是答案。

这里“答案集合”包含重复次数。例如输入1、1、2、3且k为2，答案应保留两个1；不能先放进普通set去重。内部顺序没有保证，因为Partition只解决边界，不排序前段。作者Test1打印的前k项可能不是1、2、3、4的升序。

随机Partition平均时间O(n)，最坏O(n²)，额外空间O(1)。它会交换input，调用者若需要保留原顺序必须先复制。k等于n时，目标是末下标，算法仍会执行Partition直到最后位置落位；旧页直接“返回原数组”是另一种可用优化，不是作者源码路径。

解法二：降序multiset维护最大候选

作者定义 multiset<int, greater<int>>，因此begin指向当前候选中最大的值。这个就是准入门槛：容器未满时直接插入；容器满后，新值若小于begin，删除一个begin并插入新值，否则丢弃。

#include <functional>
#include <set>
#include <vector>
 
using intSet =
    std::multiset<int, std::greater<int>>;
using setIterator = intSet::iterator;
 
void GetLeastNumbers_Solution2(
    const std::vector<int>& data,
    intSet& leastNumbers,
    int k) {
    leastNumbers.clear();
 
    if (k < 1 || data.size() < k) {
        return;
    }
 
    for (auto iter = data.begin();
         iter != data.end(); ++iter) {
        if (leastNumbers.size() < k) {
            leastNumbers.insert(*iter);
        } else {
            auto iterGreatest =
                leastNumbers.begin();
            if (*iter < *iterGreatest) {
                leastNumbers.erase(
                    iterGreatest);
                leastNumbers.insert(*iter);
            }
        }
    }
}

这个始终满足：扫描完前i项后，里面是该前缀最小的min(i,k)项。容器未满时结论显然；容器已满时，若新值不小于最大候选，它不可能进入前k；若更小，替换最大候选恰好得到新的前k。

每次插入和删除是O(log k)，总时间O(n log k)，空间O(k)。它不要求一次把全部数据装入可写数组，作者签名虽接收vector，核心更新可以直接用于流式输入。题单常把两案概括成 O(n)或O(nlogk)：前者指Partition平均复杂度，后者指有界容器；不能把Partition最坏情况也写成确定O(n)。

概念上也可用“最大堆”实现同一门槛：堆顶是最大候选，插入和弹出同为O(log k)。但作者实际源码是multiset，不是priority_queue。multiset可直接迭代全部候选且保留重复键；最大堆更紧凑，只方便访问堆顶，最终输出需逐个弹出。

两案不是只看大O符号

解法一适合数据全在内存、允许修改、追求平均线性时间的场景。解法二适合n很大、k较小、数据只读或逐项到达的场景。k接近n时，维护树的O(n log n)与全排序同阶，简单排序可能更易审计；值域很小且已知时，计数桶还能用O(n加值域)完成。

如果结果需要稳定保持输入相对顺序，两种作者方案都没有直接提供：Partition会重排，multiset按值排序。可先找第k小阈值，再第二遍按输入顺序收集小于阈值的项，并补足等于阈值的项，但这是一种新的稳定输出契约。

如果只要最小值而k等于1，单次线性扫描比通用容器更简单；作者仍通过通用两案覆盖Test4。特化是否值得取决于API热点和可维护性，不应仅因一个边界测试复制整套逻辑。

输出顺序与无效输入

作者两案有不同的。解法一把答案写进调用方数组，不返回数量或状态；无效时立即return，output保持原有内容。调用方若误读，可能看到未初始化值。解法二先clear结果容器，无效时得到确定空集合。

解法二用greater排序，迭代输出是降序4、3、2、1，而非题干列出的升序1、2、3、4。两者表示同一多重集合。若测试直接比较vector而不归一化顺序，会把正确集合误判失败；若产品承诺升序，应反向迭代或另行排序并写入接口说明。

更明确的现代接口可直接返回vector。priority_queue等价表达最大候选，结束后弹出得到降序；若API承诺升序，再reverse。输入为span即可避免复制，同时保留只读语义。

#include <algorithm>
#include <functional>
#include <queue>
#include <span>
#include <vector>
 
std::vector<int> leastNumbers(
    std::span<const int> data,
    std::size_t k) {
    if (k == 0 || k > data.size()) {
        return {};
    }
 
    std::priority_queue<int> candidates;
    for (int value : data) {
        if (candidates.size() < k) {
            candidates.push(value);
        } else if (value < candidates.top()) {
            candidates.pop();
            candidates.push(value);
        }
    }
 
    std::vector<int> result;
    result.reserve(k);
    while (!candidates.empty()) {
        result.push_back(candidates.top());
        candidates.pop();
    }
    std::reverse(result.begin(), result.end());
    return result;
}

这个版本把k等于0和k大于n都定义为空结果。若业务必须区分“合法请求恰好返回空”与“非法k”，应返回optional或expected，而不是让空vector承担两种含义。作者题目规定k为正且不大于n，但源码仍防守非法值。

作者七组测试的真实覆盖

Test函数先把原始数组复制进vector；解法一处理原始data并可能重排，解法二处理复制前的vector。作者打印expectedResult、解法一output和解法二multiset，却没有断言或比较集合，所以这是人工观察测试。

1. k为4且小于n，预期集合1、2、3、4。
2. k等于n，预期包含全部8个元素。
3. k为10且大于n，预期无结果。
4. k等于1，预期最小值1。
5. k等于0，预期无结果。
6. 输入含两个2，k为2，预期集合1、2。
7. data为空指针，n与k都为0，预期无结果。

Test6说明实现必须接受重复输入，但它没有证明“答案本身需要重复”的情形，因为最小两项是1和2。应补充1、1、3且k为2，防止误用set把两个1压成一个。还应补充负数、全部相等、已排序、逆序、k等于n时的集合完整性，以及无效调用前结果容器非空的清理行为。

作者期望数组只用于打印，不用于自动判定；解法一即使漏写某项、输出重复或集合错误，程序仍不会显示Failed。可靠测试应把结果排序后与期望多重集合比较，同时独立检查解法一输入确实允许变化、解法二输入保持不变。

#include <algorithm>
#include <cassert>
#include <vector>
 
void expectLeast(
    const std::vector<int>& input,
    std::size_t k,
    std::vector<int> expected) {
    auto actual = leastNumbers(input, k);
    std::sort(actual.begin(), actual.end());
    std::sort(expected.begin(), expected.end());
    assert(actual == expected);
}
 
void testLeastNumbers() {
    expectLeast(
        {4,5,1,6,2,7,3,8}, 4,
        {1,2,3,4});
    expectLeast({1,1,3}, 2, {1,1});
    expectLeast({-1,-5,2}, 1, {-5});
    expectLeast({2,2,2}, 3, {2,2,2});
    expectLeast({4,5,1}, 0, {});
    expectLeast({4,5,1}, 4, {});
}

随机测试可复制输入并全排序，截取前k项作为独立参考。被测结果也排序后比较，这样只验证题目要求的多重集合；若接口另承诺升序，则不要排序actual，而要直接断言顺序。

数值、内存与服务边界

k来自外部请求时，应先以与容器size相同的无符号类型解析，防止负整数转换成极大size。作者解法二先检查k小于1，利用短路求值避免负数进入data.size与k的比较；改写条件顺序时不能无意破坏这一点。

multiset每个节点有指针和分配器开销，k很大时明显高于连续堆。priority_queue底层vector通常缓存局部性更好；multiset的优势是删除任意迭代器和有序遍历，但本题只删除最大值，因此堆往往更实用。还可给multiset使用池分配器，减少逐节点分配抖动。

流式服务若需要随时查询当前最小k项，候选结构必须跨批次保存；更新逻辑与作者解法二相同。并发写入时要加锁、分片后再合并各分片Top-k，或用不可变快照。多个分片各自保留k项足以合并出全局k项，因为任何分片中排在本分片k名之后的元素不可能进入全局前k。

对浮点输入还要定义NaN顺序；对自定义对象需提供严格弱序比较器，并明确重复是按键还是按对象身份。作者int比较没有这些歧义，但把算法泛化为模板时必须补上契约。

本章练习

本章回顾

1. 只找最小k项不必完成全排序，关键是第k小选择边界。
2. Partition解法平均O(n)、O(1)额外空间，但会重排输入且前k项无序。
3. 作者第二案用降序multiset，begin始终是最大候选。
4. 有界容器时间O(n log k)、空间O(k)，支持只读和流式处理。
5. multiset保留重复值；普通set会改变题目多重集合语义。
6. 解法二迭代结果为降序，解法一顺序未定义。
7. 解法一无效时output未清空，解法二无效时结果容器被clear。
8. 作者七组测试只打印，必须增加自动集合、数量与副作用断言。

名词解释