470. 用 Rand7() 实现 Rand10()（Implement Rand10 Using Rand7）

频次 ★★★★ · 难度 🟡 · 高频：字节/腾讯

题目

已有方法 rand7() 生成 [1,7] 范围内的均匀随机整数。实现 rand10()，生成 [1,10] 范围内的均匀随机整数。

不能使用系统自带 Math.random()。

思路

拒绝采样：将 rand7() 视为一个 7 面骰子，用两次骰子生成 [1,49] 的均匀分布：

• 第一次 row = rand7()，第二次 col = rand7()
• num = (row - 1) * 7 + col 得到 [1,49] 的等概率整数
• 如果 num ≤ 40，返回 num % 10 + 1（[1,10] 均匀）
• 如果 num > 40，拒绝本轮结果，重新采样

每次采样的接受概率 p = 40/49，期望调用次数 2 * (49/40) ≈ 2.45 次，效率较高。

优化：拒绝的 [41,49] 共 9 个数，可将其映射回 [1,9] 作为一次新采样，再配合第二次拒绝采样进一步减少浪费，但实现复杂，面试掌握基础版即可。

代码

public int rand10() {
    int num;
    do {
        int row = rand7();
        int col = rand7();
        num = (row - 1) * 7 + col;
    } while (num > 40);
    return num % 10 + 1;
}

复杂度

• 时间：O(1)（期望），最坏无上界但概率极低（连续拒绝 k 次的概率 (9/49)
• 空间：O(1)

边界条件

• rand7() 保证返回 [1,7] 的整数，不需要额外校验
• num 恰好等于 40：40 % 10 + 1 = 1，正确在范围内

变式

• 用 rand5() 实现 rand7()：同样拒绝采样，列式 (rand5()-1)*5 + rand5() 得 [1,25]，取 ≤21 的，模 7 + 1
• 用 rand10() 实现 rand7()：简单拒绝即可——rand10() > 7 时拒绝，接受概率 7/10
• 优化拒绝采样：将拒绝值映射后二次采样，减少期望调用次数

易错点

• 公式 (row - 1) * 7 + col 中的乘 7 不能写成乘 6——必须确保映射到 [1,49]
• 取模范围是 % 10 + 1 映射到 [1,10]，不是 % 10（那会得到 [0,9]）
• 不要把 row 和 col 的顺序搞反，虽然对本题结果不影响，但原理上第一个维度决定”行”的跨度

面试追问

• 为什么是 > 40 拒绝，而不是 > 10？ 两次 rand7 直接生成 [1,49] 的均匀分布，如果取 > 10 就拒绝，接受率仅 10/49，效率极低。拒绝采样应尽可能提高接受率，取 40 是 7² 以内最大的 10 的倍数
• 有没有确定性的方法？ 不可能——rand7 的样本空间是 7，rand10 需要 10 种输出，7^k 永远不可能是 10 的倍数，拒绝采样是必要条件

关联题

• 同套路：478. 在圆内随机生成点 —— 拒绝采样的经典几何应用
• 进阶：528. 按权重随机选择 —— 前缀和 + 二分，不用拒绝采样
• 知识点：拒绝采样 —— 当生成空间不是目标空间整数倍时，生成一个更大的均匀空间再截断