题目重点：输入未排序、数值唯一且落在 0..32000，用 4,001 字节位图标记，再按值域扫描输出有序文件。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 值域两个端点均包含；输入每个整数最多一次，遇越界值训练代码报错。
- 训练版 getNum() 用 None 表示 EOF，putNum(value) 写一个结果；题目 helper 的精确签名未给。
- 仅需升序输出，不需保持输入顺序；内存足够容纳 32001 bits。
解题路线
- 分配 ceil(32001/8)=4001 个字节。读一个整数 v，就把 bits[v>>3] 的第 (v&7) 位设为 1。
- 输入结束后从 0 扫到 32000，凡位为 1 就调用 putNum(v)。输入无重复，因此每个 set bit 对应一个输出。
- 若输入确有重复而题目仍需保留多重性，位图会丢次数，必须改频次数组或外部排序；题目明确‘无重复’，无需擅自添加多重集语义。
- putNum 写文件失败时不能静默丢数，工程版应先写临时文件、校验输出计数后原子替换目标。
手动走一遍
输入顺序 [32000,0,8]，分别置位，扫描值域时依次输出 0、8、32000。32000 的字节下标是 4000，仍落在 4001 字节范围内；若误分配 32000 bits 会越界。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections.abc import Callable
def bitmap_sort(get_num: Callable[[], int | None], put_num: Callable[[int], None]) -> None:
"""Read until None; valid distinct input values are in [0, 32000]."""
bits = bytearray((32001 + 7) // 8)
while True:
value = get_num()
if value is None:
break
if not 0 <= value <= 32000:
raise ValueError("out-of-range value")
bits[value >> 3] |= 1 << (value & 7)
for value in range(32001):
if bits[value >> 3] & (1 << (value & 7)):
put_num(value)
if __name__ == "__main__":
source = iter([32000, 0, 8])
output = []
bitmap_sort(lambda: next(source, None), output.append)
assert output == [0, 8, 32000]
复杂度
读 N 个数 O(N)，扫完整个值域 M=32001 为 O(M)，总 O(N+M) 时间；位图 ceil(M/8)=4001 字节，外加常数工作空间。输出文件容量 O(N)。
易错点与追问
容易失分的边界
- 值域为 0..32000 共 32001 个值，位图少分配一位。
- 把题目无重复改成有重复仍用 bitset 并声称保留原频次。
- 边读边输出无法保证有序。
- 假定 getNum 的 EOF 一定是 -1；题目未明确 helper 细节，训练版明确用 None。
继续深挖
- 如果数值范围是 0..10^12 而 N 很稀疏，为什么位图不合适？
- 若输入有重复且要输出重复，计数桶或外排如何选？
- 如果 PutNum 必须流式立即调用且不能等读完，是否仍能保证排序？
