LeetCode 470 这道题很多人第一次看到题目描述都会愣一下我已经有 Rand7() 了想生成 1 到 10那直接rand7() % 10 1不就行了真不行。这道题最折磨人的地方在于它要求你只调用给定的rand7()不碰任何系统随机源最后输出 1 到 10 的均匀分布。说白了你手里只有一个七面骰子却要模拟一个十面骰子而且每个面出现的概率必须完全相等。刷算法题的人、准备算法面试的人、做随机化系统的人都值得花半小时把这道题吃透——代码虽然只有几行但背后的概率思维和工程取舍非常典型。1. 题目到底在问什么很多题解上来就直接给公式我反而觉得应该先搞明白题目到底在限制什么、为什么这样限制。只有理解了约束你才知道为什么答案是拒绝采样而不是某种取模技巧。1.1 为什么需要“用低范围生成高范围”现实世界里的随机数生成器往往只能覆盖某个固定范围。比如很多单片机上的硬件随机源只能输出 0 到 1你要生成 0 到 999 就得自己“拼”。加密协议、A/B 测试、蒙特卡洛模拟里都有类似的场景底层只给你一个均匀的随机接口上层却需要另一个范围的随机数。LeetCode 470 把这个场景抽象成了一个算法题给你一个能等概率生成 1 到 7 的 APIrand7()请你只通过调用它来实现rand10()也就是等概率生成 1 到 10。注意限定词是“只通过调用它”意味着你不能直接用系统时钟、不能开数组做映射表、更不能起一个线程去抢 CPU 然后取某个寄存器值。所有的随机性都必须来自rand7()的输出。这其实就是用已知的离散均匀分布去构造任意指定范围的离散均匀分布。题目没有限制调用次数也没有限制你能不能拒绝一部分结果这就给拒绝采样留下了空间。想通了这一点后面的解法就是顺理成章的事。1.2 三个“一看就懂但全错”的常规解法先别急着看答案我自己当年也是先踩了一堆坑。下面三种思路几乎每个初学者都会想过但全都不对。尝试写法输出范围问题所在rand7() % 10 11~10rand7()只产生 1~7取模后 8~10 的样本根本不存在rand7() * rand7() % 10 11~10乘积空间里每个数字的出现路径数不同非均匀(rand7() rand7()) / 21~7多个均匀变量求和会趋向钟形分布中间值概率更高先随机到 1~7再用 if 映射成 8~101~10条件分支导致映射后的概率完全错乱逐个说。rand7() % 10 1看起来最自然但实际上rand7() % 10的结果就是 1~7因为 7 比 10 小取模不改变结果8~10 永远不可能出现范围都不对更别说均匀了。rand7() * rand7()则更隐蔽。乍一看乘积范围是 1~49取模后好像能用。但你把所有组合列出来就会发现1 只能由 1×1 产生2 可以由 1×2、2×1 产生4 却可以由 1×4、4×1、2×2 三种方式产生。不同的数对应的产生路径数不一样均匀性没了。至于加法你可以自己掷两枚七面骰子做实验结果的和会大量聚集在中间值附近这是中心极限定理在起作用。所以这三个方案要么范围错了要么均匀性错了都不能要。2. 核心原理构造等概率空间 拒绝采样正确的解法分两步先用两次rand7()构造一个更大的等概率样本空间然后把多余的部分拒绝掉。这一步叫拒绝采样是整个题目的灵魂。2.1 两次 Rand7() 如何生成 1~49一次rand7()只有 7 种结果两次调用就有 7×749 种组合。关键问题是怎么把这 49 种组合映射成 49 个等概率的数字。最经典的写法是x (rand7() - 1) * 7 rand7();这里rand7() - 1得到 0~6乘以 7 之后相当于把第一个结果变成了“高位”第二个结果变成了“低位”。你可以把它理解成一个七进制数只不过进制范围是 0~6 而不是 0~9。枚举一下第一次返回 1第二次返回 1 → x 1第一次返回 1第二次返回 7 → x 7第一次返回 2第二次返回 1 → x 8第一次返回 7第二次返回 7 → x 49由于两次调用相互独立任意一组(第一次, 第二次)出现的概率都是 1/49所以 x 在 1~49 上均匀分布。这一步是整个算法的地基。有个细节很容易写错有人图省事写成rand7() * 7 rand7()这样 x 的值域变成 8~56虽然每个值仍然唯一对应一组组合但你得到的是一个从 8 开始的区间后续取模和判断边界都会变得别扭。用(rand7() - 1) * 7让样本空间从 1 开始后续处理清爽很多。2.2 拒绝采样的数学证明现在手里有 1~49 的均匀分布目标是 1~10。问题是 49 不是 10 的整数倍直接取模会导致某些数字比别的数字多一次出现机会。解决办法很直接1~40 正好是 10 的 4 倍我们就只保留 1~40把 41~49 这 9 个数字丢弃重新采样。这就是拒绝采样。为什么丢弃后依然均匀因为每个输出值 k 在 1~40 中都有 4 个对应的 x 值输出 1对应 x 1, 11, 21, 31输出 2对应 x 2, 12, 22, 32...输出 10对应 x 10, 20, 30, 40所以在“本次尝试落在 1~40”的条件下每个 k 被选中的概率都是 4/40 1/10。严谨一点还可以计算无条件概率。设每次尝试成功的概率 p 40/49。要输出 k需要前 n-1 次都失败落在 41~49第 n 次成功且恰好落在 k 对应的 4 个样本上。于是P(输出 k) Σ(n1→∞) (9/49)^(n-1) × (4/49) (4/49) / (1 - 9/49) (4/49) / (40/49) 1/10这就是拒绝采样均匀性的完整证明。很多面试官会追问“为什么丢掉 41~49 不会破坏均匀性”上面这个无穷级数求和就是标准答案。2.3 为什么不能直接用加法和乘法一步到位聊到这里你会发现“构造等概率空间”和“直接对原始数字做运算”是两回事。直接加、直接乘本质上是在原分布上做非线性变换均匀性大概率被破坏。拒绝采样的优雅之处在于它先构造一个足够大的均匀空间再去掉多余的部分而不是试图扭曲原有的概率分布。打个比方要把 49 个等概率小球放进 10 个相同大小的箱子里每个箱子必须装 4 个球。如果直接硬塞有的箱子会多一个有的少一个。拒绝采样就是先把多余的 9 个球扔掉让剩下的 40 个球能恰好平均分到 10 个箱子。这样虽然有点浪费但结果是绝对均匀的。3. 完整代码实现与精度验证原理通了代码其实非常短。但短代码里同样有讲究边界条件和返回值映射都值得仔细检查。3.1 C 标准题解与边界说明LeetCode 上最标准的 C 写法是class Solution { public: int rand10() { int x; do { x (rand7() - 1) * 7 rand7(); } while (x 40); return (x - 1) % 10 1; } };几个细节要注意。x 40这个判断包含了等号也就是 x 等于 40 时可以用等于 41 时拒绝。如果把写成40 永远不会被接受输出 1 的概率直接少一半分布必挂。(x - 1) % 10 1保证了返回值落在 1~10。这里用x - 1而不是直接用x是因为题目要求返回 1~10而不是 0~9。如果你写成x % 10 1虽然也能得到 1~10但映射关系会整体偏移1 会映射到 210 会映射到 1表面上依然均匀但读代码的人很容易晕。用(x - 1) % 10 1更直观1 到 1、2 到 2、10 到 10。3.2 用 Python 跑 100 万次统计检查均匀性光说均匀不算数代码写出来要能验证。我在本地用 Python 模拟了 100 万次输出顺便统计了rand7()的实际调用次数。import random random.seed(42) call_count [0] def rand7(): call_count[0] 1 return random.randint(1, 7) def rand10(): while True: x (rand7() - 1) * 7 rand7() if x 40: return (x - 1) % 10 1 samples 1_000_000 counts [0] * 10 for _ in range(samples): counts[rand10() - 1] 1 print(counts:, counts) print(calls:, call_count[0]) print(avg calls per result:, call_count[0] / samples)某次运行结果是这样的counts: [100294, 99981, 100023, 100052, 99956, 100031, 99879, 100104, 99788, 99892] calls: 2449852 avg calls per result: 2.449852每个数字的出现次数都在 10 万左右最大偏差约 294占比 0.029%这是随机波动下的正常表现。平均每次输出消耗 2.449852 次rand7()调用非常接近理论值 2.45。3.3 关于随机种子和测试可信度本地模拟时别忘了设置随机种子。不设置的话每次运行结果都不同虽然不影响验证结论但不方便复现。我在代码里用了random.seed(42)让每次跑出来的计数表都完全一致方便跟别人对结论。测试次数也很关键。只跑 1000 次就下结论说“不均匀”往往会误判。随机波动下每个桶的计数偏差会很大。我自己的习惯是至少跑 10 万次能跑 100 万次更好。对算法题来说统计验证不只是为了证明正确性更是为了让自己对“均匀”有直观感受即使算法完全正确10 万次采样下每个桶也会有几百的浮动看到这种波动不用慌。4. 期望调用次数这道题真正的进阶考点很多题解讲完代码就结束了但面试官真正爱追问的是这个算法平均要调用多少次rand7()这既是概率论基础也是评估算法效率的关键指标。4.1 从几何分布推导平均调用次数每次尝试我们需要调用两次rand7()生成 x成功条件是x 40。因为 x 均匀分布在 1~49所以单次尝试的成功率p 40 / 49 ≈ 0.8163失败率是 9/49。每轮尝试互相独立需要的尝试次数 T 服从几何分布期望是E[T] 1 / p 49 / 40 ≈ 1.225每次尝试要调用两次rand7()所以总的期望调用次数E[calls] 2 × E[T] 2 × 49 / 40 98 / 40 2.45也就是说平均每生成一个 1~10 的输出需要调用rand7()约 2.45 次。这个数字跟前面的模拟结果 2.449852 高度吻合。理解这个期望很重要。它意味着大部分时候一两次就成功了但偶尔会连续失败好多次。连续失败 4 次的概率是 (9/49)^4 ≈ 0.0011千分之一左右连续失败 10 次的概率已经小到 (9/49)^10 ≈ 1.5e-8几乎不可能发生。这就是拒绝采样的典型特征平均效率很好但最坏情况没有上界。4.2 信息复用一种更极端的优化思路标准解法直接把 41~49 全部丢弃其实这 9 个数字并不是完全没有信息量。你想x 落在 41~49 时x - 41得到的是 0~8 的均匀随机数。如果下次继续调用rand7()就可以把这个 0~8 和一个新的 0~6 组合起来构造出更大的样本空间从而降低拒绝率。具体思路是第一次 x 落在 1~40直接输出落在 41~49则缓存 r x - 410~8。下一轮再调用一次rand7()得到 y rand7() - 10~6组合成r * 7 y得到一个 0~62 的均匀数保留 0~59拒绝 60~62。这样成功率从 40/49 提升到了 60/63同时第二轮只消耗了 1 次rand7()调用另一个随机数来自缓存。总体期望调用次数可以降到 2.2 左右。这个优化在面试里属于加分项能说出思路已经很有深度但千万不要在基础解法还没写对的时候就跳上去写。一方面代码复杂度陡增容易出 bug另一方面面试官可能只是想验证你对基础拒绝采样是否掌握过度优化反而喧宾夺主。4.3 复杂度与最坏情况说明时间复杂度方面每次尝试都是常数时间的判断尝试次数服从几何分布因此平均时间复杂度是 O(1)。最坏情况下循环可能持续非常久但概率趋近于 0所以按期望分析是合理的。空间复杂度很简单只用了常数个变量O(1)。这也是这道题的另一个优点不需要额外的随机数表不需要预先生成一批随机结果完全在线生成。在工程上如果你的系统对延迟非常敏感比如某个高并发接口要求每次响应时间必须控制在 1 毫秒以内那“平均 O(1)、无上限”的算法就要谨慎使用。一个常见做法是设置最大尝试次数如果超过上限就退化成某种保底方案避免极端情况下的长尾延迟。5. 常见问题与排查技巧实录刷题过程中我见过不少人代码逻辑看着没问题但测试结果就是不对。这里把高频踩坑点整理出来供你对照排查。5.1 测试结果不均匀的 3 个常见原因第一个原因是用rand7() * rand7()当样本空间。这个前面已经演示过乘积分布天然不均匀再怎么取模都不行。误用这个写法测试结果必然在某些数字上明显偏高。第二个原因是边界条件写错。尤其是x 40和x 40的差别以及返回值写成x % 10 1与(x - 1) % 10 1的差别。x 40会让 40 这个样本被丢弃输出 1 的概率少一半。x % 10 1虽然分布均匀但输出范围变成了 1~10 的偏移映射很多人自己测着测着就糊涂了。第三个原因是采样次数太少。随机算法天然有波动跑 1000 次看到某个数字多出几十次很容易误判为“算法不均匀”。我的建议是最少跑 10 万次并且用多组随机种子重复验证不要用一次测试结果下结论。5.2 面试官高频追问与回答思路追问一为什么 x 在 41~49 时要丢弃而不是继续取模答案是取模会让样本空间无法被 10 整除最终输出非均匀。丢弃后条件概率公式保证了均匀性。追问二期望调用多少次rand7()答案是 2.45 次推导过程见 4.1 节。这是最常被问的问题建议手推一遍几何分布别只背结论。追问三反过来给你rand10()怎么实现rand7()很简单调用rand10()如果结果小于等于 7 就返回否则重新调用。这就是同一个拒绝采样模板的逆向应用。追问四如果rand7()调用很昂贵怎么优化答信息复用把被拒绝区间的随机性缓存下来降低后续调用次数。能准确回答到这个层面基本就稳了。追问五有没有可能做到完全不拒绝让每次都能成功生成不可能。rand7()的样本空间是 7 的幂次永远不可能被 10 整除所以一定存在至少一个多余样本需要处理。这个“不可能性”往往是面试官用来考察你数学底子的杀手锏。5.3 工程场景里“拒绝采样”的迁移拒绝采样不只是算法题的套路很多主流库里都有它的影子。Java 的ThreadLocalRandom内部处理范围随机数时就有类似逻辑蒙特卡洛模拟里生成特定分布随机数也经常用拒绝采样连 Box-Muller 生成高斯分布时都有一层变换和判断。理解了 LeetCode 470你再看那些库的源码会更容易读懂它们为什么把随机数范围对半截断、为什么有时候循环重试。工程上使用拒绝采样记得注意两点一是给循环加一个尝试次数上限防止极端情况下拖垮服务二是用统计手段压测分布是否真的均匀尤其是随机数源本身的位数和返回范围可能导致偏差。很多看起来随机的问题最后排查下来都是底层随机源在某些区间不均匀导致的。6. 从这道题延伸出去的个人经验关于这道题我还想借机聊聊刷题和面试之外的东西。因为 LeetCode 470 虽然短小但它代表了一整类问题的解题范式。6.1 拒绝采样题型的通用套路凡是“用 A 范围随机生成 B 范围等概率”的题都可以套三步多次调用 A组合出至少覆盖 B 范围的等概率样本空间。将样本空间截断成 B 的整数倍。丢弃多余部分循环直到命中有效样本。第 1 步用乘法扩展维度第 2 步用取模映射第 3 步用拒绝保证均匀。这个模板可以推广。比如用rand7()实现rand100()你可以调用 3 次rand7()构造 1~343 的样本空间保留 1~300成功率 300/343 ≈ 87.5%。虽然效率不是最优但思路完全一样。6.2 刷题时如何避免“背题解”LeetCode 热门 100 题里像这种代码短但原理深的题还有很多。我自己的经验是不要急着看题解先亲手把错误方案跑一遍亲眼看到分布不均在数据上长什么样再写正确版本并证明它均匀。这个过程比背十道题都管用。特别是这道题如果你直接背代码三分钟就背完了但你永远不会理解“为什么是 40 而不是 49”也回答不了面试官那句“那你能证明它是均匀的吗”。6.3 一个值得长期养成的验证习惯任何涉及随机算法的实现都不要凭感觉说“应该没问题”。我自己的固定流程是写计数数组跑 N 次采样观察每个桶的数量是否在合理偏差内统计实际调用次数跟理论期望值比对。如果这三个检查都通过我才敢说这个随机算法大概率是对的。以前我写随机数相关代码总喜欢凭感觉说“应该没问题”。后来有一次线上模拟实验的分布偏了排查半天才发现是底层随机数生成器的某个范围不均匀造成的从此我养成了任何随机逻辑都要跑统计验证的习惯。回到 LeetCode 470代码短不代表简单真正有价值的是你能否证明它均匀、能否算出期望调用次数、能否在面试官追问时接住。把这三点吃透这道题才算真正刷完了。
用Rand7实现Rand10：拒绝采样与均匀随机数生成原理
LeetCode 470 这道题很多人第一次看到题目描述都会愣一下我已经有 Rand7() 了想生成 1 到 10那直接rand7() % 10 1不就行了真不行。这道题最折磨人的地方在于它要求你只调用给定的rand7()不碰任何系统随机源最后输出 1 到 10 的均匀分布。说白了你手里只有一个七面骰子却要模拟一个十面骰子而且每个面出现的概率必须完全相等。刷算法题的人、准备算法面试的人、做随机化系统的人都值得花半小时把这道题吃透——代码虽然只有几行但背后的概率思维和工程取舍非常典型。1. 题目到底在问什么很多题解上来就直接给公式我反而觉得应该先搞明白题目到底在限制什么、为什么这样限制。只有理解了约束你才知道为什么答案是拒绝采样而不是某种取模技巧。1.1 为什么需要“用低范围生成高范围”现实世界里的随机数生成器往往只能覆盖某个固定范围。比如很多单片机上的硬件随机源只能输出 0 到 1你要生成 0 到 999 就得自己“拼”。加密协议、A/B 测试、蒙特卡洛模拟里都有类似的场景底层只给你一个均匀的随机接口上层却需要另一个范围的随机数。LeetCode 470 把这个场景抽象成了一个算法题给你一个能等概率生成 1 到 7 的 APIrand7()请你只通过调用它来实现rand10()也就是等概率生成 1 到 10。注意限定词是“只通过调用它”意味着你不能直接用系统时钟、不能开数组做映射表、更不能起一个线程去抢 CPU 然后取某个寄存器值。所有的随机性都必须来自rand7()的输出。这其实就是用已知的离散均匀分布去构造任意指定范围的离散均匀分布。题目没有限制调用次数也没有限制你能不能拒绝一部分结果这就给拒绝采样留下了空间。想通了这一点后面的解法就是顺理成章的事。1.2 三个“一看就懂但全错”的常规解法先别急着看答案我自己当年也是先踩了一堆坑。下面三种思路几乎每个初学者都会想过但全都不对。尝试写法输出范围问题所在rand7() % 10 11~10rand7()只产生 1~7取模后 8~10 的样本根本不存在rand7() * rand7() % 10 11~10乘积空间里每个数字的出现路径数不同非均匀(rand7() rand7()) / 21~7多个均匀变量求和会趋向钟形分布中间值概率更高先随机到 1~7再用 if 映射成 8~101~10条件分支导致映射后的概率完全错乱逐个说。rand7() % 10 1看起来最自然但实际上rand7() % 10的结果就是 1~7因为 7 比 10 小取模不改变结果8~10 永远不可能出现范围都不对更别说均匀了。rand7() * rand7()则更隐蔽。乍一看乘积范围是 1~49取模后好像能用。但你把所有组合列出来就会发现1 只能由 1×1 产生2 可以由 1×2、2×1 产生4 却可以由 1×4、4×1、2×2 三种方式产生。不同的数对应的产生路径数不一样均匀性没了。至于加法你可以自己掷两枚七面骰子做实验结果的和会大量聚集在中间值附近这是中心极限定理在起作用。所以这三个方案要么范围错了要么均匀性错了都不能要。2. 核心原理构造等概率空间 拒绝采样正确的解法分两步先用两次rand7()构造一个更大的等概率样本空间然后把多余的部分拒绝掉。这一步叫拒绝采样是整个题目的灵魂。2.1 两次 Rand7() 如何生成 1~49一次rand7()只有 7 种结果两次调用就有 7×749 种组合。关键问题是怎么把这 49 种组合映射成 49 个等概率的数字。最经典的写法是x (rand7() - 1) * 7 rand7();这里rand7() - 1得到 0~6乘以 7 之后相当于把第一个结果变成了“高位”第二个结果变成了“低位”。你可以把它理解成一个七进制数只不过进制范围是 0~6 而不是 0~9。枚举一下第一次返回 1第二次返回 1 → x 1第一次返回 1第二次返回 7 → x 7第一次返回 2第二次返回 1 → x 8第一次返回 7第二次返回 7 → x 49由于两次调用相互独立任意一组(第一次, 第二次)出现的概率都是 1/49所以 x 在 1~49 上均匀分布。这一步是整个算法的地基。有个细节很容易写错有人图省事写成rand7() * 7 rand7()这样 x 的值域变成 8~56虽然每个值仍然唯一对应一组组合但你得到的是一个从 8 开始的区间后续取模和判断边界都会变得别扭。用(rand7() - 1) * 7让样本空间从 1 开始后续处理清爽很多。2.2 拒绝采样的数学证明现在手里有 1~49 的均匀分布目标是 1~10。问题是 49 不是 10 的整数倍直接取模会导致某些数字比别的数字多一次出现机会。解决办法很直接1~40 正好是 10 的 4 倍我们就只保留 1~40把 41~49 这 9 个数字丢弃重新采样。这就是拒绝采样。为什么丢弃后依然均匀因为每个输出值 k 在 1~40 中都有 4 个对应的 x 值输出 1对应 x 1, 11, 21, 31输出 2对应 x 2, 12, 22, 32...输出 10对应 x 10, 20, 30, 40所以在“本次尝试落在 1~40”的条件下每个 k 被选中的概率都是 4/40 1/10。严谨一点还可以计算无条件概率。设每次尝试成功的概率 p 40/49。要输出 k需要前 n-1 次都失败落在 41~49第 n 次成功且恰好落在 k 对应的 4 个样本上。于是P(输出 k) Σ(n1→∞) (9/49)^(n-1) × (4/49) (4/49) / (1 - 9/49) (4/49) / (40/49) 1/10这就是拒绝采样均匀性的完整证明。很多面试官会追问“为什么丢掉 41~49 不会破坏均匀性”上面这个无穷级数求和就是标准答案。2.3 为什么不能直接用加法和乘法一步到位聊到这里你会发现“构造等概率空间”和“直接对原始数字做运算”是两回事。直接加、直接乘本质上是在原分布上做非线性变换均匀性大概率被破坏。拒绝采样的优雅之处在于它先构造一个足够大的均匀空间再去掉多余的部分而不是试图扭曲原有的概率分布。打个比方要把 49 个等概率小球放进 10 个相同大小的箱子里每个箱子必须装 4 个球。如果直接硬塞有的箱子会多一个有的少一个。拒绝采样就是先把多余的 9 个球扔掉让剩下的 40 个球能恰好平均分到 10 个箱子。这样虽然有点浪费但结果是绝对均匀的。3. 完整代码实现与精度验证原理通了代码其实非常短。但短代码里同样有讲究边界条件和返回值映射都值得仔细检查。3.1 C 标准题解与边界说明LeetCode 上最标准的 C 写法是class Solution { public: int rand10() { int x; do { x (rand7() - 1) * 7 rand7(); } while (x 40); return (x - 1) % 10 1; } };几个细节要注意。x 40这个判断包含了等号也就是 x 等于 40 时可以用等于 41 时拒绝。如果把写成40 永远不会被接受输出 1 的概率直接少一半分布必挂。(x - 1) % 10 1保证了返回值落在 1~10。这里用x - 1而不是直接用x是因为题目要求返回 1~10而不是 0~9。如果你写成x % 10 1虽然也能得到 1~10但映射关系会整体偏移1 会映射到 210 会映射到 1表面上依然均匀但读代码的人很容易晕。用(x - 1) % 10 1更直观1 到 1、2 到 2、10 到 10。3.2 用 Python 跑 100 万次统计检查均匀性光说均匀不算数代码写出来要能验证。我在本地用 Python 模拟了 100 万次输出顺便统计了rand7()的实际调用次数。import random random.seed(42) call_count [0] def rand7(): call_count[0] 1 return random.randint(1, 7) def rand10(): while True: x (rand7() - 1) * 7 rand7() if x 40: return (x - 1) % 10 1 samples 1_000_000 counts [0] * 10 for _ in range(samples): counts[rand10() - 1] 1 print(counts:, counts) print(calls:, call_count[0]) print(avg calls per result:, call_count[0] / samples)某次运行结果是这样的counts: [100294, 99981, 100023, 100052, 99956, 100031, 99879, 100104, 99788, 99892] calls: 2449852 avg calls per result: 2.449852每个数字的出现次数都在 10 万左右最大偏差约 294占比 0.029%这是随机波动下的正常表现。平均每次输出消耗 2.449852 次rand7()调用非常接近理论值 2.45。3.3 关于随机种子和测试可信度本地模拟时别忘了设置随机种子。不设置的话每次运行结果都不同虽然不影响验证结论但不方便复现。我在代码里用了random.seed(42)让每次跑出来的计数表都完全一致方便跟别人对结论。测试次数也很关键。只跑 1000 次就下结论说“不均匀”往往会误判。随机波动下每个桶的计数偏差会很大。我自己的习惯是至少跑 10 万次能跑 100 万次更好。对算法题来说统计验证不只是为了证明正确性更是为了让自己对“均匀”有直观感受即使算法完全正确10 万次采样下每个桶也会有几百的浮动看到这种波动不用慌。4. 期望调用次数这道题真正的进阶考点很多题解讲完代码就结束了但面试官真正爱追问的是这个算法平均要调用多少次rand7()这既是概率论基础也是评估算法效率的关键指标。4.1 从几何分布推导平均调用次数每次尝试我们需要调用两次rand7()生成 x成功条件是x 40。因为 x 均匀分布在 1~49所以单次尝试的成功率p 40 / 49 ≈ 0.8163失败率是 9/49。每轮尝试互相独立需要的尝试次数 T 服从几何分布期望是E[T] 1 / p 49 / 40 ≈ 1.225每次尝试要调用两次rand7()所以总的期望调用次数E[calls] 2 × E[T] 2 × 49 / 40 98 / 40 2.45也就是说平均每生成一个 1~10 的输出需要调用rand7()约 2.45 次。这个数字跟前面的模拟结果 2.449852 高度吻合。理解这个期望很重要。它意味着大部分时候一两次就成功了但偶尔会连续失败好多次。连续失败 4 次的概率是 (9/49)^4 ≈ 0.0011千分之一左右连续失败 10 次的概率已经小到 (9/49)^10 ≈ 1.5e-8几乎不可能发生。这就是拒绝采样的典型特征平均效率很好但最坏情况没有上界。4.2 信息复用一种更极端的优化思路标准解法直接把 41~49 全部丢弃其实这 9 个数字并不是完全没有信息量。你想x 落在 41~49 时x - 41得到的是 0~8 的均匀随机数。如果下次继续调用rand7()就可以把这个 0~8 和一个新的 0~6 组合起来构造出更大的样本空间从而降低拒绝率。具体思路是第一次 x 落在 1~40直接输出落在 41~49则缓存 r x - 410~8。下一轮再调用一次rand7()得到 y rand7() - 10~6组合成r * 7 y得到一个 0~62 的均匀数保留 0~59拒绝 60~62。这样成功率从 40/49 提升到了 60/63同时第二轮只消耗了 1 次rand7()调用另一个随机数来自缓存。总体期望调用次数可以降到 2.2 左右。这个优化在面试里属于加分项能说出思路已经很有深度但千万不要在基础解法还没写对的时候就跳上去写。一方面代码复杂度陡增容易出 bug另一方面面试官可能只是想验证你对基础拒绝采样是否掌握过度优化反而喧宾夺主。4.3 复杂度与最坏情况说明时间复杂度方面每次尝试都是常数时间的判断尝试次数服从几何分布因此平均时间复杂度是 O(1)。最坏情况下循环可能持续非常久但概率趋近于 0所以按期望分析是合理的。空间复杂度很简单只用了常数个变量O(1)。这也是这道题的另一个优点不需要额外的随机数表不需要预先生成一批随机结果完全在线生成。在工程上如果你的系统对延迟非常敏感比如某个高并发接口要求每次响应时间必须控制在 1 毫秒以内那“平均 O(1)、无上限”的算法就要谨慎使用。一个常见做法是设置最大尝试次数如果超过上限就退化成某种保底方案避免极端情况下的长尾延迟。5. 常见问题与排查技巧实录刷题过程中我见过不少人代码逻辑看着没问题但测试结果就是不对。这里把高频踩坑点整理出来供你对照排查。5.1 测试结果不均匀的 3 个常见原因第一个原因是用rand7() * rand7()当样本空间。这个前面已经演示过乘积分布天然不均匀再怎么取模都不行。误用这个写法测试结果必然在某些数字上明显偏高。第二个原因是边界条件写错。尤其是x 40和x 40的差别以及返回值写成x % 10 1与(x - 1) % 10 1的差别。x 40会让 40 这个样本被丢弃输出 1 的概率少一半。x % 10 1虽然分布均匀但输出范围变成了 1~10 的偏移映射很多人自己测着测着就糊涂了。第三个原因是采样次数太少。随机算法天然有波动跑 1000 次看到某个数字多出几十次很容易误判为“算法不均匀”。我的建议是最少跑 10 万次并且用多组随机种子重复验证不要用一次测试结果下结论。5.2 面试官高频追问与回答思路追问一为什么 x 在 41~49 时要丢弃而不是继续取模答案是取模会让样本空间无法被 10 整除最终输出非均匀。丢弃后条件概率公式保证了均匀性。追问二期望调用多少次rand7()答案是 2.45 次推导过程见 4.1 节。这是最常被问的问题建议手推一遍几何分布别只背结论。追问三反过来给你rand10()怎么实现rand7()很简单调用rand10()如果结果小于等于 7 就返回否则重新调用。这就是同一个拒绝采样模板的逆向应用。追问四如果rand7()调用很昂贵怎么优化答信息复用把被拒绝区间的随机性缓存下来降低后续调用次数。能准确回答到这个层面基本就稳了。追问五有没有可能做到完全不拒绝让每次都能成功生成不可能。rand7()的样本空间是 7 的幂次永远不可能被 10 整除所以一定存在至少一个多余样本需要处理。这个“不可能性”往往是面试官用来考察你数学底子的杀手锏。5.3 工程场景里“拒绝采样”的迁移拒绝采样不只是算法题的套路很多主流库里都有它的影子。Java 的ThreadLocalRandom内部处理范围随机数时就有类似逻辑蒙特卡洛模拟里生成特定分布随机数也经常用拒绝采样连 Box-Muller 生成高斯分布时都有一层变换和判断。理解了 LeetCode 470你再看那些库的源码会更容易读懂它们为什么把随机数范围对半截断、为什么有时候循环重试。工程上使用拒绝采样记得注意两点一是给循环加一个尝试次数上限防止极端情况下拖垮服务二是用统计手段压测分布是否真的均匀尤其是随机数源本身的位数和返回范围可能导致偏差。很多看起来随机的问题最后排查下来都是底层随机源在某些区间不均匀导致的。6. 从这道题延伸出去的个人经验关于这道题我还想借机聊聊刷题和面试之外的东西。因为 LeetCode 470 虽然短小但它代表了一整类问题的解题范式。6.1 拒绝采样题型的通用套路凡是“用 A 范围随机生成 B 范围等概率”的题都可以套三步多次调用 A组合出至少覆盖 B 范围的等概率样本空间。将样本空间截断成 B 的整数倍。丢弃多余部分循环直到命中有效样本。第 1 步用乘法扩展维度第 2 步用取模映射第 3 步用拒绝保证均匀。这个模板可以推广。比如用rand7()实现rand100()你可以调用 3 次rand7()构造 1~343 的样本空间保留 1~300成功率 300/343 ≈ 87.5%。虽然效率不是最优但思路完全一样。6.2 刷题时如何避免“背题解”LeetCode 热门 100 题里像这种代码短但原理深的题还有很多。我自己的经验是不要急着看题解先亲手把错误方案跑一遍亲眼看到分布不均在数据上长什么样再写正确版本并证明它均匀。这个过程比背十道题都管用。特别是这道题如果你直接背代码三分钟就背完了但你永远不会理解“为什么是 40 而不是 49”也回答不了面试官那句“那你能证明它是均匀的吗”。6.3 一个值得长期养成的验证习惯任何涉及随机算法的实现都不要凭感觉说“应该没问题”。我自己的固定流程是写计数数组跑 N 次采样观察每个桶的数量是否在合理偏差内统计实际调用次数跟理论期望值比对。如果这三个检查都通过我才敢说这个随机算法大概率是对的。以前我写随机数相关代码总喜欢凭感觉说“应该没问题”。后来有一次线上模拟实验的分布偏了排查半天才发现是底层随机数生成器的某个范围不均匀造成的从此我养成了任何随机逻辑都要跑统计验证的习惯。回到 LeetCode 470代码短不代表简单真正有价值的是你能否证明它均匀、能否算出期望调用次数、能否在面试官追问时接住。把这三点吃透这道题才算真正刷完了。