LeetCode 470. 用 Rand7() 实现 Rand10()
目录
题目描述
题意分析
给定一个黑盒
rand7()，它等概率返回1..7中的整数；要求实现rand10()，等概率返回1..10中的整数。「等概率」是硬性要求：
1..10每个数出现的概率必须严格等于1/10，「差不多均匀」不算对——评测和面试官都会从分布上验证。唯一可用的随机源就是
rand7()，不能调用语言自带的随机函数；除此之外调用次数不限，题目只是鼓励尽量少调用。难点在于
7与10互质：单次调用只有7种等概率结果，无论套什么确定性变换都造不出10种等概率结果，所以必须组合多次调用，并想清楚组合之后的分布长什么样。
解法：拒绝采样构造等概率空间
核心思路
两次独立的
rand7()可以编码出0..48共49个等概率状态：value = (rand7() - 1) * 7 + rand7() - 1。
49不能被10整除，因此只接受0..39，再用value % 10 + 1映射到1..10。每个结果恰好对应4个状态；落入40..48时重新采样。
解题步骤
- 调用两次
rand7()，按七进制位组合成0..48的均匀随机数。- 若结果小于
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)$。
关键点总结
- 进制编码保持有序对与随机状态一一对应，因此仍然均匀。
- 接受区间的状态数必须是
10的倍数，才能等分给十个结果。- 拒绝采样保证严格等概率，不能为保证固定次数而强行映射剩余状态。
易错点总结
- 将两次结果相加会得到三角分布，并非均匀分布。
- 对全部
49个状态直接取模，会让部分结果多对应一个状态。- 使用零基编号时应接受
value < 40，写成<= 40会纳入41个状态。- 被拒绝后必须重新生成完整的有序对，不能只重掷其中一次。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 478. 在圆内随机生成点 | 中等 | 几何区域上的拒绝采样 |
| 528. 按权重随机选择 | 中等 | 前缀和加二分把均匀随机变成加权随机 |
| 384. 打乱数组 | 中等 | Fisher–Yates 洗牌保证排列等概率 |
| 382. 链表随机节点 | 中等 | 蓄水池抽样应对未知长度的数据流 |
| 398. 随机数索引 | 中等 | 蓄水池抽样在重复元素索引上的应用 |