如何在O(log n + s)时间内从[1..n]中等概率采样不在集合S中的数？

嘿，针对这个「给定n和大小为s（s远小于n）的集合S，要等概率采样[1..n]中不在S里的数k」的问题，我来梳理下已知方案，再聊聊目标复杂度的可行性：

现有方案的优缺点 #

1. 朴素数组过滤法 #

这个思路非常直白：先把[1..n]里所有不在S中的元素挑出来组成新数组，再随机选数组里的元素。

• 致命缺点：时间复杂度是O(n)，当n很大的时候（比如百万、亿级），生成这个数组的成本完全无法接受，直接pass。

2. 拒绝采样法 #

这是实际场景里常用的方案：直接随机生成一个[1..n]的数，如果它在S里就重新生成，直到拿到符合要求的数。

• 优点：实现超简单，而且因为s远小于n，平均下来几乎一次就能中，实用性拉满。
• 硬伤：没有理论时间上限——极端情况可能连续抽到S里的元素（虽然概率极低），从最坏时间复杂度的角度看，不符合我们的目标。

关于O(log n + s)复杂度方案的可行性 #

目前还没法确定这个目标是否能实现，但可以从这个方向尝试推导：

1. 先把集合S排序，这一步的时间是O(s log s)，因为s远小于n，这个成本相对可以忽略，甚至可以归到O(s)的量级里。
2. 计算有效候选数的总数：m = n - s，先随机生成一个[1..m]的数x。
3. 接下来要把x映射到[1..n]中排除S后的第x个元素——这一步可以用二分查找，快速定位S中小于等于某个数的元素数量，从而调整x得到最终的k，二分查找的时间是O(log s)。

整体来看，这个思路的时间复杂度接近O(s + log n)，但还需要更严谨的验证：比如是否能严格保证等概率，以及最坏情况下的时间是否真的能被控制在O(log n + s)内，目前还没有定论。

内容的提问来源于stack exchange，提问作者A1m