LeetCode 470. 用 Rand7() 实现 Rand10()
题目描述
题意分析
已有的
rand7()每次独立、等概率地返回1到7，只能调用它来实现rand10()，让1到10每个数的返回概率都严格等于十分之一，不能调用其他随机函数。关键不仅是让结果落在正确范围内，还要让十种结果的概率相同。直接将两次结果相加，会因为不同和值对应的组合数量不同而产生偏差；把不够整分的状态直接取模，也会让部分结果出现得更多。
可以先构造更大的等概率状态空间，只保留能平均分成十组的部分，再把各组映射为输出。基础解法将其余状态丢弃重试；题目进阶要求减少
rand7()调用次数，可以进一步复用这些被拒绝的状态。
解法：拒绝采样构造等概率空间
核心思路
[!blue]
两次独立调用
rand7()，得到有序对(a, b)，共有7 × 7 = 49种等概率结果。用(a - 1) * 7 + b - 1把它们依次编号为0到48：第一项决定七个一组的哪一组，第二项决定组内位置，不同有序对不会得到同一个编号，所以这些编号仍然均匀。
49不能被10整除，直接取模会导致九个余数比另一个余数多对应一个状态。因此只接受前40个编号，即0到39，再返回value % 10 + 1。这时每个余数都恰好有四个等概率编号与之对应，十种输出就具有相同概率。若编号落在
40到48，不产生输出，重新调用两次rand7()开始下一轮。新一轮与上一轮独立，且每轮接受的十种结果始终等概率，所以增加重试次数不会偏向某个输出。不能设置固定重试上限后随意返回一个值，那会把剩余概率额外分配给某些结果。每轮成功概率为
40/49，设期望轮数为E，总会先执行一轮，只有以9/49的概率失败时才重新开始，所以E = 1 + (9/49)E，解得E = 49/40。每轮固定调用两次，因此平均调用次数为2 × 49/40 = 2.45。
解题步骤
- 调用两次
rand7()，计算value = (rand7() - 1) * 7 + rand7() - 1，得到0到48的均匀编号。- 若
value < 40，返回value % 10 + 1。- 否则本轮不输出，重新生成完整的有序对，重复上述过程。
代码实现
class Solution extends SolBase {
public int rand10() {
while (true) {
// 两个独立七等分结果一一映射成四十九个等概率状态。
int value = (rand7() - 1) * 7 + rand7() - 1;
// 只接受四十个状态，每个输出恰好对应四个状态。
if (value < 40) {
return value % 10 + 1;
}
}
}
}
func rand10() int {
for {
// 两个独立七等分结果一一映射成四十九个等概率状态。
value := (rand7()-1)*7 + rand7() - 1
// 只接受四十个状态，每个输出恰好对应四个状态。
if value < 40 {
return value%10 + 1
}
}
}
复杂度分析
- 时间复杂度：期望 $O(1)$，每轮接受概率为
40/49，期望调用rand7()的次数为2 × 49/40 = 2.45；理论最坏次数无上界。- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 进制编码保持有序对与随机状态一一对应，因此仍然均匀。
- 接受区间的状态数必须是
10的倍数，才能等分给十个结果。- 拒绝采样保证严格等概率，不能为保证固定次数而强行映射剩余状态。
解法二：复用被拒绝的随机状态
核心思路
[!blue]
基础解法把
40到48全部丢弃，但“已经落入这个区间”并不意味着随机性消失。在这个条件下，九个值仍然等概率出现，减去40就得到一个均匀的0到8。将它与一次新的独立rand7()组合，可以得到9 × 7 = 63个等概率编号，无需重新调用两次。具体计算
(value - 40) * 7 + rand7() - 1，得到0到62。前60个状态可以平均分为十组，因此value < 60时直接返回value % 10 + 1，每个输出对应六个状态。若第二阶段仍被拒绝，编号必在
60到62，三个值在这一条件下依然等概率。减去60后，再与一次新的rand7()组合，得到3 × 7 = 21个等概率编号。接受前20个，每个输出对应两个状态；只剩编号20无法等分，此时才重新开始整轮。三个阶段都只对各自均匀状态中的十倍数区间取模，因此无论在哪一阶段返回，十种输出都等概率。优化的是被拒绝后的处理方式，不是强行把不整分的状态塞进答案；每次复用前先减去区间起点，才能把条件均匀的剩余状态重新编号。
一轮总要先调用两次；以
9/49的概率需要第三次，以(9/49) × (3/63) = 3/343的概率需要第四次。四次之后还要重新开始的概率只有(9/49) × (3/63) × (1/21) = 1/2401，因此比基础方案减少了重新取样的开销。
解题步骤
- 用两次调用生成
0..48；若小于40，取模返回。- 否则将剩余九个状态重新编号，再调用一次生成
0..62；若小于60，取模返回。- 否则将剩余三个状态重新编号，再调用一次生成
0..20；若小于20，取模返回。- 若第三阶段也被拒绝，回到第一步重新开始。
代码实现
class Solution extends SolBase {
public int rand10() {
while (true) {
int value = (rand7() - 1) * 7 + rand7() - 1;
if (value < 40) {
return value % 10 + 1;
}
value = (value - 40) * 7 + rand7() - 1;
if (value < 60) {
return value % 10 + 1;
}
value = (value - 60) * 7 + rand7() - 1;
if (value < 20) {
return value % 10 + 1;
}
}
}
}
func rand10() int {
for {
value := (rand7()-1)*7 + rand7() - 1
if value < 40 {
return value%10 + 1
}
value = (value-40)*7 + rand7() - 1
if value < 60 {
return value%10 + 1
}
value = (value-60)*7 + rand7() - 1
if value < 20 {
return value%10 + 1
}
}
}
复杂度分析
- 时间复杂度：期望 $O(1)$。设期望调用次数为
E，有E = 2 + 9/49 + 3/343 + E/2401，解得E = 329/150，约为2.193次。理论最坏调用次数仍没有固定上界。- 空间复杂度：$O(1)$，仅使用一个状态变量和循环。
关键点总结
[!green]
- 剩余区间仍有均匀随机性：失败只说明值落在指定范围，范围内各值的条件概率仍然相同。
- 先归零再组合新状态：依次减去
40、60，才能正确构造9 × 7与3 × 7个等概率状态。- 只接受整十个状态：三个阶段分别接受
40、60、20个状态，取模后才不会偏向某些输出。
易错点总结
[!yellow]
- 将两次结果相加会得到三角分布，并非均匀分布。
- 对全部
49个状态直接取模，会让部分结果多对应一个状态。- 使用零基编号时应接受
value < 40，写成<= 40会纳入41个状态。- 基础方案被拒绝后应重新生成完整有序对；若要复用随机性，必须按剩余区间重新编号，不能固定原来的一项后直接沿用旧映射。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 478. 在圆内随机生成点 | 中等 | 同样可用拒绝采样，从等概率的较大空间中拒绝不合适区域以保持目标分布均匀。 |