470. 用 Rand7() 实现 Rand10()
题目描述
已经提供函数 rand7()，每次调用都会均匀随机地返回 1 到 7 中的一个整数。
请实现 rand10()，使它均匀随机地返回 1 到 10 中的一个整数。实现中只能调用 rand7()，不能使用语言自带的其他随机函数。
测试时有一个内部参数 n，表示 rand10() 会被调用多少次；它不会作为参数传给 rand10()。输出是这 n 次调用的结果数组。
输入：n = 1 输出：[2]
解释：结果随机，只要落在 1 到 10 之间即可。
输入：n = 2 输出：[9,1]
解释：两次调用的结果随机，这里只是一种可能。
输入：n = 3 输出：[2,2,10]
解释：三次调用的结果随机，这里只是一种可能。
数据范围
1 <= n <= 10^5
进阶：平均每次 rand10() 要调用多少次 rand7()？能否尽量减少调用次数？
解题思路：拒绝采样
一次 rand7() 只有 7 种结果，不够 10 种。调用两次，把 (row, col) 看成 7×7 表格中的一格，编号 idx = (row-1)*7 + col，在 1–49 上均匀分布。取前 40 格，它们恰好能平均分成 10 组，每组 4 格，用 1 + (idx-1) % 10 映射；落在 41–49 就拒绝，重新抽。这叫“拒绝采样”。
为什么正确
被接受的 idx 在 1–40 上均匀分布，而 1–40 中每个余数类恰好 4 个，所以返回值在 1–10 上均匀。
复杂度分析
每轮被接受的概率 40/49，期望约 1.225 轮、2.45 次 rand7()；额外空间 O(1)。
易错点
常见错误是 rand7() + rand7() 或 rand7() * rand7()：和与积的分布并不均匀。必须用“(row-1)*7 + col”构造均匀的 1–49，再拒绝多余的部分。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def rand10(self) -> int:
while True:
row = rand7()
col = rand7()
idx = (row - 1) * 7 + col
if idx <= 40:
return 1 + (idx - 1) % 10class Solution extends SolBase {
public int rand10() {
while (true) {
int row = rand7();
int col = rand7();
int idx = (row - 1) * 7 + col;
if (idx <= 40) {
return 1 + (idx - 1) % 10;
}
}
}
}class Solution {
public:
int rand10() {
while (true) {
int row = rand7();
int col = rand7();
int idx = (row - 1) * 7 + col;
if (idx <= 40) {
return 1 + (idx - 1) % 10;
}
}
}
};func rand10() int {
for {
row := rand7()
col := rand7()
idx := (row-1)*7 + col
if idx <= 40 {
return 1 + (idx-1)%10
}
}
}var rand10 = function() {
while (true) {
const row = rand7();
const col = rand7();
const idx = (row - 1) * 7 + col;
if (idx <= 40) {
return 1 + (idx - 1) % 10;
}
}
};function rand10(): number {
while (true) {
const row = rand7();
const col = rand7();
const idx = (row - 1) * 7 + col;
if (idx <= 40) {
return 1 + (idx - 1) % 10;
}
}
}其他解法
基础拒绝采样简单可靠；复用版本在相同正确性下减少了 rand7 的期望调用次数，体现了随机数复用的优化思路。
解法 2：拒绝采样 + 复用被拒绝的随机数 时间 期望 O(1)，空间 O(1)
第一轮用两次 rand7 得到均匀的 1~49，落在 1~40 就直接映射到 1~10。落在 41~49 时，idx−40 本身就是均匀的 1~9，再调用一次 rand7 组合成均匀的 1~63，落在 1~60 就映射返回。再被拒绝时，余下的 1~3 与 rand7 组合成 1~21，取 1~20。三轮都失败才从头开始。
把被拒绝的样本中残留的随机性继续利用起来，期望调用 rand7 的次数从约 2.45 降到约 2.19。代码多出两轮，需要理解“被拒绝的部分仍是均匀分布”。
class Solution:
def rand10(self) -> int:
while True:
# 第一轮：rand7 × rand7 得到 1~49，取前 40 个
idx = (rand7() - 1) * 7 + rand7()
if idx <= 40:
return 1 + (idx - 1) % 10
# 被拒绝的 41~49 本身是均匀的 1~9，再乘一个 rand7 得到 1~63
idx = (idx - 41) * 7 + rand7()
if idx <= 60:
return 1 + (idx - 1) % 10
# 被拒绝的 61~63 是均匀的 1~3，再乘一个 rand7 得到 1~21
idx = (idx - 61) * 7 + rand7()
if idx <= 20:
return 1 + (idx - 1) % 10class Solution extends SolBase {
public int rand10() {
while (true) {
int idx = (rand7() - 1) * 7 + rand7();
if (idx <= 40) return 1 + (idx - 1) % 10;
idx = (idx - 41) * 7 + rand7();
if (idx <= 60) return 1 + (idx - 1) % 10;
idx = (idx - 61) * 7 + rand7();
if (idx <= 20) return 1 + (idx - 1) % 10;
}
}
}class Solution {
public:
int rand10() {
while (true) {
int idx = (rand7() - 1) * 7 + rand7();
if (idx <= 40) return 1 + (idx - 1) % 10;
idx = (idx - 41) * 7 + rand7();
if (idx <= 60) return 1 + (idx - 1) % 10;
idx = (idx - 61) * 7 + rand7();
if (idx <= 20) return 1 + (idx - 1) % 10;
}
}
};func rand10() int {
for {
idx := (rand7()-1)*7 + rand7()
if idx <= 40 {
return 1 + (idx-1)%10
}
idx = (idx-41)*7 + rand7()
if idx <= 60 {
return 1 + (idx-1)%10
}
idx = (idx-61)*7 + rand7()
if idx <= 20 {
return 1 + (idx-1)%10
}
}
}var rand10 = function() {
while (true) {
let idx = (rand7() - 1) * 7 + rand7();
if (idx <= 40) return 1 + (idx - 1) % 10;
idx = (idx - 41) * 7 + rand7();
if (idx <= 60) return 1 + (idx - 1) % 10;
idx = (idx - 61) * 7 + rand7();
if (idx <= 20) return 1 + (idx - 1) % 10;
}
};function rand10(): number {
while (true) {
let idx = (rand7() - 1) * 7 + rand7();
if (idx <= 40) return 1 + (idx - 1) % 10;
idx = (idx - 41) * 7 + rand7();
if (idx <= 60) return 1 + (idx - 1) % 10;
idx = (idx - 61) * 7 + rand7();
if (idx <= 20) return 1 + (idx - 1) % 10;
}
}