1MB内存也能找第k小？按位分块两趟扫描算法详解

最近在洛谷刷题的时候遇到了 P15799 这道“找数”第一眼看上去平平无奇不就是给 n 个数找第 k 小的数嘛排序一下甚至直接用 nth_element 都能做。但真正动手提交的时候才发现这道题最恶心的地方根本不是算法本身而是它给的内存限制。1MB你没看错就是 1024KB。n 最大能到 10^7你光是把这堆数塞进一个 int 数组40MB 就没了。所以这道题真正考你的是怎么在几乎不能存储原始数据的情况下还能快速找到第 k 小的数。这篇文章我就从思路推导、代码实现到踩坑细节完整复盘一遍我自己的做法希望能给准备挑战这道题的朋友一个可复现的参考。先说结论这道题的正解是基于“按位分块统计”的两趟扫描做法用空间换时间的老套路在这里反过来了是用时间换空间。第一趟扫描统计每个高位区间内的数字个数确定答案落在哪个区间第二趟扫描只关心这个区间内的数字继续用低位桶计数最终拼出完整的答案。整个过程中只需要两个长度为 65536 的 int 数组加起来 512KB稳稳卡在内存限制内。下面我会把每一步拆开讲包括我是怎么想到这个方案的、代码里有哪些容易写错的细节、以及实际提交时遇到的各种坑。1. 题目到底在考什么读题先看限制1.1 数据规模带来的连锁反应先说数据范围。题目要求从 n 个整数中找出第 k 小的数n 最大能到 10^7k 同样在合法范围内。这是什么概念如果你平时习惯了 O(n log n) 的排序这题直接给你把这条路堵死了。不是时间复杂度不行1e7 个数的 sort 在 OJ 上其实勉强能跑但内存才是真正的杀手。一个 int 占 4 字节1e7 个 int 就是 40MB超过了常见的 256MB 限制也就罢了问题是这题只有 1MB。1MB 意味着什么能放下的 int 数量上限是 262144 个。也就是说你别说存所有数据了就是开一个大小为 1e6 的标记数组都直接爆内存。这种情况下任何需要“先把所有数读进来再处理”的经典算法比如std::sort 直接排序std::nth_element 快速选择归并排序中途统计把全部数读进 vector 再操作全部阵亡。因为它们都基于一个前提数据能同时存在于内存中。而这题的前提恰恰是“数据不允许留在内存里”。1.2 为什么堆也不行看起来可行细算就崩很多人第一反应是用堆做维护一个大小为 k 的大根堆遍历所有数遇到比堆顶小的就替换最后堆顶就是第 k 小。这个思路本身没问题时间复杂度 O(n log k)空间是 O(k)。但你把 k 的上限代入进去看看。k 最大可以是 1e7那这个堆在最坏情况下要装 1e7 个 int又是 40MB。也许你会说k 不一定会取到最大值OJ 数据不会那么狠。但是作为解题你必须考虑最坏情况。这题既然敢给 1MB 限制就是逼着你在任何 k 值下都能通过。堆方案在最坏情况下不合格所以它也不是正解。那怎么办关键点在于我们并不需要真的“记住”每个数只需要记住“每个区间里有多少个数”。这就是分块计数的雏形。2. 核心思路像查字典一样逐层缩小范围2.1 从“区间人数统计”说起我用一个生活化的例子来解释最终采用的算法。假设你是一所学校的教务老师学生有 1 万人每个人的学号都是 8 位数字。现在要找学号第 k 小的学生但你不允许把所有学号抄到纸上。你会怎么做第一轮只看学号前两位代表年级。你让学生按年级排队报数统计出高一 2000 人、高二 3000 人、高三 5000 人。如果 k2500你立刻知道要找的人在“高二”这个组里并且是高二学生中的第 500 名。第二轮只看高二学生学号的第三、四位代表班级。让高二学生按班级报数统计出高二 1 班 50 人、2 班 60 人……累加找到第 500 名落在哪个班。继续这样按位分组每次都缩小范围最终就能确定唯一的学号。这个例子里的“前两位”“第三四位”就是对数字按二进制位切分。电脑里的 int 是 32 位二进制数我们可以先看高 16 位再看低 16 位把 2^32 个可能值分成 65536 个大组每个大组再分成 65536 个小组。恰好两个 int 数组就能装下所有计数内存完全可控。2.2 为什么是 16 位内存和效率的平衡点选择按 16 位切分不是随意的。假设我们按高 8 位分组那只有 256 个组每组跨度 2^24第二轮扫描时依然要在 1600 多万个可能值里精确定位这就不算“快速缩小”了。反过来说如果按高 24 位分组那组数有 1600 多万每个组用 int 计数就得 64MB直接超内存。16 位这个切分点非常巧妙组数量 2^16 65536每个组一个 int 计数数组占用 65536 × 4B 256KB第二轮的低位桶同样 256KB两份数组加起来 512KB距离 1MB 还有一半余量从时间上看两趟扫描的代价是 O(2n)也就是 2e7 次循环配合快读完全能接受。这就是典型的“用两倍时间换 40 倍内存”在内存受限题里是必须学会的套路。2.3 和快速选择、基数排序的关系本质上这个算法是基数排序Radix Sort思想的变体。基数排序按位分配到桶我们不需要完整排序只需要根据计数决定第 k 小元素所在的桶然后递归到桶内继续找。只不过这里只递归了一层因为 32 位数字分两次 16 位处理刚好能确定唯一值。如果你熟悉快速选择算法可以把它理解为一种确定性的“按位二分”每次根据某一位把所有数划分成两组然后根据计数决定走哪边。快速选择靠随机 pivot 期望 O(n)而按位分组靠二进制固定切分稳定 O(n) 且不需要存数据非常适合这种内存极小的场景。3. 完整实现与逐步拆解3.1 代码全貌下面是我调通的完整 C 代码。为了压缩篇幅去掉了不必要的头文件但核心逻辑都在。#include cstdio #include cstring #include algorithm const int GROUP_NUM 1 16; const int MASK (1 16) - 1; int highCnt[GROUP_NUM]; int lowCnt[GROUP_NUM]; inline int readInt() { int x 0, sign 1; char c getchar(); while (c 0 || c 9) { if (c -) sign -1; c getchar(); } while (c 0 c 9) { x x * 10 (c - 0); c getchar(); } return x * sign; } int main() { int n, k; n readInt(); k readInt(); // k 从 1 开始 for (int i 0; i n; i) { int x readInt(); unsigned u (unsigned)x 2147483648u; // 负数偏移处理 highCnt[u 16]; } long long sum 0; int targetHigh 0; for (int i 0; i GROUP_NUM; i) { if (sum highCnt[i] k) { targetHigh i; break; } sum highCnt[i]; } long long remain k - sum; // 在目标高16位区间内的第 remain 小 fseek(stdin, 0, SEEK_SET); // 重置输入准备第二次扫描 for (int i 0; i GROUP_NUM; i) lowCnt[i] 0; for (int i 0; i n; i) { int x readInt(); unsigned u (unsigned)x 2147483648u; if ((u 16) targetHigh) { lowCnt[u MASK]; } } int targetLow 0; for (int i 0; i GROUP_NUM; i) { remain - lowCnt[i]; if (remain 0) { targetLow i; break; } } unsigned ans ((unsigned)targetHigh 16) | (unsigned)targetLow; int finalAns (int)(ans - 2147483648u); printf(%d\n, finalAns); return 0; }3.2 负数处理一个很容易被忽视的点题目并没有保证所有输入都是非负数。如果直接把负数当作 int 读入x 16的操作对负数来说是算术右移最高位补 1结果会出现负数下标直接数组越界。解决办法是先把 int 映射到无符号范围。我用的是u (unsigned)x 2147483648u。这个偏移量的含义是把 int 范围 [-2^31, 2^31-1] 整体平移到 [0, 2^32-1]这样所有输入都变成了无符号整数之后的所有位运算都是定义良好的。最后输出时再减去偏移量还原。这个处理方式比用abs()之类的函数要严谨得多因为你不能改变数的相对大小关系平移不会改变序关系所以可以安全使用。3.3 第 k 小和下标细节这道题的 k 是从 1 开始计数的也就是说 k1 表示最小的那个数。我在第一轮累加计数时用的是if (sum highCnt[i] k) { targetHigh i; break; }这个判断的含义是把前 i 组的人数累加起来如果加上当前组的人数后覆盖到了 k说明第 k 小的数一定在当前这个高 16 位区间里。注意是 k不是 k如果sum highCnt[i] k说明第 k 个数恰好是当前组里的最大那个也应该归入当前组。第二轮用remain继续定位低 16 位。这里我也踩过坑直接把remain - lowCnt[i]; if (remain 0)判断其中remain是 long long 类型。如果用 intk最大 1e7理论上 int 也放得下但为了稳妥避免任何边界溢出用 long long 更好。3.4 为什么需要 fseek 重置输入流整个算法需要扫两遍输入。第一遍统计高 16 位分组第二遍只统计目标分组内部的数字。所以必须有能力“把输入流倒回去重新读”。在洛谷的评测环境下标准输入是通过文件重定向进来的所以fseek(stdin, 0, SEEK_SET)基本是有效的。但这里有个隐含问题我的readInt()函数用的是getchar()如果第一遍读到最后输入流的位置在文件末尾那么fseek能回到开头继续读。如果你在本地用管道或手动输入的方式测试fseek 可能会失败因为管道不可寻址。这种问题在 OJ 上一般不会出现但如果你本地调试遇到建议把测试输入改成文件重定向比如./a.out input.txt这样就模拟了评测环境fseek 也就正常了。4. 实测中遇到的典型问题与排查记录4.1 问题第一次提交 MLE数组开大了我最开始写的时候犯了个低级错误开了两个int highCnt[1 18]和int lowCnt[1 18]想着多一点余量。结果每个数组 1MB两个就 2MB直接超出限制。后来我认真算了一遍账高 16 位最多只有 65536 种取值低 16 位也只有 65536 种取值两个数组各 65536 就够了。256KB 256KB 512KB剩下的 512KB 留给栈和其他开销稳得很。教训就是内存受限题任何数组大小都要先做计算别凭感觉开。4.2 问题用 cin/cout 导致 TLE刚上手时我图省事直接cin读入。n1e7即使开了ios::sync_with_stdio(false)标准输入在极端数据下也非常吃力。后来我换成了自己实现的getchar()快读实测速度提升非常明显。实际上还可以更激进一点用fread整块读入再解析性能会更好。但我给的版本已经能在洛谷时限内通过所以快读就够用了。如果你追求极限可以再封装一个fread缓冲版的readInt原理一样。4.3 问题负数输入导致数组越界 Runtime Error这是我第一次遇到 RE 的原因。当时我直接用x 16负数右移后高位补 1得到的下标是负数访问数组越界。这个问题排查了很久最后用printf调试发现下标变成负数了。修复方式就是前面提到的偏移映射。补充一点(unsigned)x 2147483648u这个操作不会改变二进制位模式只是把符号位当作数值的一部分。对负数来说映射后的大小关系和原来的大小关系一致所以排序和找 k 小不受影响。4.4 问题fseek 后读入错乱有朋友在本地用 IDE 的“运行”按钮直接往标准输入里贴数据测试发现 fseek 没效果第二遍读不到东西。这是因为 IDE 的输入是管道或交互终端不是可寻址的文件流。解决办法是改用文件输入。在命令行里用重定向./main test.in这样 stdin 指向的是文件fseek 才能正常工作。如果你用的是评测环境基本不用担心。4.5 快速排查表现象可能原因解决办法输出错一位k 的起始语义搞错或/判断用错明确 k 从 1 开始检查累计条件数组越界 / RE负数右移产生负数下标用无符号偏移映射MLE分组数开太大严格控制数组长度为 65536两个数组共 512KBTLEcin 读入太慢使用getchar()快读或 fread本地测试第二遍读不到数输入源不是文件fseek 失败改用文件重定向输入输出结果偏大或偏小低 16 位拼装时位移优先级错误用括号明确(u16 16) | (lo)5. 这道题还能怎么扩展从 P15799 学到的通用套路5.1 由“找第 k 小”到“找中位数/第 k 大”如果你掌握了分块秒数的思想把第 k 小改成第 k 大几乎零成本。只需要把“第 k 大”转换成“第 (n-k1) 小”剩下的逻辑完全一样。中位数就是 k n/2 或 n/21 的特殊情况两趟扫描依然可以处理。5.2 扩展到任意值域的多趟扫描我这次用了两次 16 位切分因为 int 是 32 位。如果题目给的是 64 位整数内存又限制得很死你可以改成 4 趟每趟处理 16 位或者 8 趟每趟处理 8 位。时间会翻倍但内存依然是可控的。这就是“以时间换空间”的极致体现。这也让我想到一个经验面对内存受限题第一步不是想高级算法而是先统计你的内存预算。1MB 能放下多少个 int能放下多少个长度为多少的数组把预算算清楚再去设计切分方案思路会清晰很多。5.3 和其他“流式”算法对比这种两趟扫描的思路本质上是一种流式算法数据从头到尾流过两次每次只保留压缩后的统计信息。相比单趟的流式算法比如水库抽样、布隆过滤器它的优势是精确答案、无需随机性劣势是必须允许数据源可重读。如果输入来自网络流或磁带这类不可重读的介质就得另想办法比如单趟维护堆但要接受最坏情况下内存不足的风险。从这个角度看P15799 真正考察的是一种“资源约束下的方案权衡”能力。它不问你知不知道 nth_element而是问你能不能放弃绚烂的算法老老实实用两趟扫描去解决问题。这种能力在实际工程里同样重要——数据量大到一定程度时很多优雅的算法都会因为内存而失效。6. 一些实战调试心得最后分享几个我折腾这道题时的体会可能对你帮助更大内存预算一定要写进代码注释里。比如我会在数组定义旁标注256KB这样以后调参时不会稀里糊涂把数组翻倍。调试阶段可以先把 n 缩小加一些printf验证分组逻辑。比如 n10k3手动算一遍答案再用代码跑一遍。逐组打印 highCnt 的值能很快定位思路问题。注意fseek(stdin, 0, SEEK_SET)之后如果你之前用getchar()读到了EOF有些环境下流的错误标志可能还残留。稳妥起见可以在fseek后调用clearerr(stdin)。洛谷上不加也能过但本地用 MSVC 环境时我遇到过问题加上更保险。能不用 STL 就不要用 STL。在内存受限题里一个vector的底层分配可能就会打破你的预算。如果你在第二次扫描时发现 lowCnt 始终为 0先检查第一轮统计 targetHigh 是否正确。我在调试时遇到过因为偏移量写错导致同一组数字在两次扫描中映射不一致的问题排查了很久才发现是偏移处理写了两套不同的常量。这道题我前前后后大概提交了七八次才完全通过WA、RE、MLE、TLE 各踩了一遍。但正是这种全方位“教育”让我对内存受限下的算法设计有了远超刷普通题的深刻理解。如果你也在卡这道题别急着看题解先自己推导一遍 16 位分块的过程再动手写收获会大得多。