面试真题整理

1. 一亿个数选出最大的100个

多方面考虑，全面回答

（1）流式/内存受限：固定大小最小堆

维护一个大小为100的最小堆

先把前100个数建堆，之后每读到一个新数 x：若 x > heap_min，弹出堆顶并压入 x；否则丢弃。扫描完毕，堆中即为最大的100个；如需从大到小输出，再做一次 O(k log k) 的排序即可。

时间复杂度：O(n log k)（这里 log 100 很小，常数低，单次比较少）。

空间复杂度：O(k)。

优点：一次遍历、可在线处理、适合数据在磁盘/流式来源、实现简单且稳定。

（2）内存足够一次装下数据：选择算法（Quickselect）

值得一提的是，C++中std::nth_element也是基于Quickselect实现的。 详见GPT的分析

思路：找出第100大的“阈值”t，使得 ≥t 的恰好100个（含重复）。

• 用 Quickselect 在平均 O(n) 时间内把数组划分为“≥t”和“<t”的两部分。

• 取“≥t”的前100个，再 O(k log k) 排序输出。

复杂度：

• 平均时间 O(n)；最坏 O(n^2)（可用 BFPRT/Median-of-Medians 将最坏收敛到 O(n)，但常数大、实现复杂）。

• 空间：原地 O(1) 额外空间。

优点：一次性内存足够时，理论更优；缺点是实现难度与最坏情况风险。

（3）外部存储/分布式：分块 Top-k + 归并

单机外存（数据在多文件/磁盘上）：

• 把数据按块读取（如每块装内存的 1/10~1/50），对每块用“最小堆法”求局部 top-100。

• 将所有块的候选（块数×100，数量远小于 n）再用一次“最小堆法”或排序得到全局 top-100。

MapReduce(如Hadoop)/分布式：

• Mapper：对分片做局部 top-100 输出。

• Reducer：对所有候选合并为全局 top-100。 复杂度：每块 O(m log k)，合并 O((B·k) log k)（B为块/分片数）。I/O 友好，工程可落地。

（4）值域已知且较小：桶计数/直方图

若数值是非负整数且值域 R 不大（如 ≤1e7）：

• 计数排序思路建立频次数组 cnt[0..R]，自大到小累计直到覆盖100个元素，输出对应的值（处理重复频次）。

复杂度：O(n + R)；对大值域或浮点数不适用。

（5）并行化实现要点

• 多线程：每线程处理一段数据，维护本地最小堆（无锁），最后把所有线程的候选（线程数×k）在主线程再合并一次。

• NUMA/缓存友好：分块处理、减少跨核共享；堆操作集中在小内存块，命中率高。

• 避免假共享：多线程输出的统计/结果结构体要按 64B cache line 填充对齐，别把多个线程的计数写到同一行。

• GPU：常用做全局选择/分段排序（如 radix select + top-k 归并），工程复杂度更高。