DeepSeek LeetCode 470. 用 Rand7() 实现 Rand10() Java实现

思路：拒绝采样（Rejection Sampling）

核心问题：Rand7() 生成 1~7 均匀随机数，目标是生成 1~10 均匀随机数。7 和 10 没有倍数关系，需要先扩大取值范围再取模映射。

基本构造：两次调用 Rand7() 可以生成 1~49 的均匀随机数：

x = (rand7() – 1) * 7 + rand7()

(rand7()-1) 生成 0~6 的 7 进制高位，rand7() 生成 1~7 的低位，组合得到 1~49，每个值概率都是 1/49。

· 若 x <= 40，直接取模映射：(x – 1) % 10 + 1，能得到均匀的 1~10（因为 40 是 10 的倍数，每组 4 个值恰好对应一个结果）。
· 若 x ∈ [41, 49]，说明落在"浪费区间"，重新采样。

这就是最简版本。但 49 个数中浪费了 9 个，可以把浪费的 9 个数继续利用，进一步降低期望调用次数。

Java 实现：优化版（利用被拒绝的余数）

/**
* The rand7() API is already defined in the parent class SolBase.
* public int rand7();
* @return a random integer in the range 1 to 7
*/
class Solution extends SolBase {
public int rand10() {
while (true) {
// 第一次：1 ~ 49
int x = (rand7() – 1) * 7 + rand7();
if (x <= 40) {
return (x – 1) % 10 + 1;
}

// x ∈ [41, 49]，共 9 个数，映射到 [1, 9]
x = (x – 41) * 7 + rand7(); // 1 ~ 63
if (x <= 60) {
return (x – 1) % 10 + 1;
}

// x ∈ [61, 63]，共 3 个数，映射到 [1, 3]
x = (x – 61) * 7 + rand7(); // 1 ~ 21
if (x <= 20) {
return (x – 1) % 10 + 1;
}
// x = 21 则重新循环
}
}
}

代码说明

· 第一次采样：x ∈ [1, 49]，x <= 40 直接返回，否则进入第二次。
· 第二次采样：把 [41, 49] 平移到 [0, 8]，再乘 7 加 rand7()，得到 [1, 63]。x <= 60 直接返回，否则进入第三次。
· 第三次采样：把 [61, 63] 平移到 [0, 2]，再乘 7 加 rand7()，得到 [1, 21]。x <= 20 直接返回，否则只剩 x = 21，重新循环。

注意 (x – 41) * 7 + rand7() 中 x – 41 的范围是 0~8，(x-41)*7 范围 0~56，加 rand7() 后为 1~63，确保每个值等概率。

为什么 (x – 1) % 10 + 1 是均匀的？

以第一次为例，1~40 共 40 个数，每个数概率 1/49。按 (x-1)%10+1 分组：

结果 对应 x
1 1, 11, 21, 31
2 2, 12, 22, 32
… …
10 10, 20, 30, 40

每组恰好 4 个数，概率都是 4/49，因此均匀。

期望调用次数分析

阶段 触发概率 消耗 rand7 次数
第一次成功 40/49 2
第二次成功 (9/49) * (60/63) 4
第三次成功 (9/49) * (3/63) * (20/21) 6
循环 剩余极小 —

期望调用次数 ≈ 2 × (40/49) + 4 × (9/49)(60/63) + 6 × (9/49)(3/63)(20/21) + … ≈ 2.376 次，优于简单版本的约 2.45 次。

复杂度

· 时间复杂度：期望 O(1)，期望调用 rand7() 约 2.376 次。
· 空间复杂度：O(1)。

易错点

优化版中余数平移要写对：(x – 41) 而不是 (x – 40)，因为 41 要映射到 0。