470. 用 Rand7() 实现 Rand10()

LeetCode 470 原题链接

题目描述

已知题目提供的 rand7() 可以等概率返回 [1, 7] 中的一个整数，要求只调用 rand7()，实现一个等概率返回 [1, 10] 中整数的 rand10()。

这里有两个容易忽略的前提：

rand7() 的 7 种结果等概率，即每个结果出现的概率都是 1/7。
多次调用 rand7() 相互独立，因此两个有序结果 (a, b) 出现的概率都是 1/49。

题目会多次调用 rand10() 并检查输出分布。由于结果是随机的，示例中的具体输出不是固定答案；需要证明的是每个整数 1～10 出现的概率都严格等于 1/10。

面试结论

连续调用两次 rand7()，可以等概率生成 1～49：

(rand7() - 1) * 7 + rand7()

只接受 1～40，拒绝 41～49 并重新采样。因为 40 能被 10 整除，再用 (num - 1) % 10 + 1 映射到 1～10，每个结果都恰好对应 4 个原始值，所以结果严格均匀。

题目本质

题目不是简单地把 rand7() 的返回值“变换”成 1～10，而是要保持每个结果的概率都为 1/10。

如果直接取模，例如 rand7() % 10 + 1，最多只能得到 2～8；即使通过多次调用扩大范围，如果原始状态数不能被 10 整除，直接取模仍会使部分结果拥有更多映射，产生概率偏差。

核心方法是拒绝采样：先构造足够大的等概率样本空间，再只保留大小为 10 的整数倍的部分。

解题过程

一次 rand7() 能等概率得到 7 种结果。两次独立调用形成 49 个等概率的有序组合：

第一次：决定所在的 7 个数区间
第二次：决定区间内的位置

(rand7() - 1) * 7 + rand7() => [1, 49]

其中 1～40 可以平均分成 10 组，每组 4 个数：

1、11、21、31  -> 1
2、12、22、32  -> 2
...
10、20、30、40 -> 10

41～49 无法均匀分组，因此丢弃并重新生成。

为什么这个公式能均匀生成 1～49

先不要看公式，先看两次 rand7() 到底产生了什么。

设第一次结果是 first，第二次结果是 second。一次调用有 7 种可能，两次调用便有下面这些有序组合：

(1, 1)、(1, 2)、...、(1, 7)
(2, 1)、(2, 2)、...、(2, 7)
...
(7, 1)、(7, 2)、...、(7, 7)

一共有 7 × 7 = 49 个组合。由于两次调用独立且每个结果的概率都是 1/7，任意一个指定组合的概率都是：

P(first = a 且 second = b)
= P(first = a) × P(second = b)
= 1/7 × 1/7
= 1/49

因此，我们已经拥有了 49 个等概率的随机状态。现在缺少的只是：把这 49 个状态分别编号为 1～49，并保证没有两个状态拿到相同编号。

公式是怎样构造出来的

可以把 49 个组合摆成一个 7 × 7 的表格：第一次结果决定行，第二次结果决定列。

                    第二次 rand7()
                 1   2   3   4   5   6   7

第一次 rand7() 1   1   2   3   4   5   6   7
              2   8   9  10  11  12  13  14
              3  15  16  17  18  19  20  21
              4  22  23  24  25  26  27  28
              5  29  30  31  32  33  34  35
              6  36  37  38  39  40  41  42
              7  43  44  45  46  47  48  49

(first - 1) × 7 + second

这个公式可以拆成两部分理解：

(first - 1) × 7：前面完整的行一共有多少个格子
second：当前格子在本行排第几个

之所以要 first - 1，是因为位于第 1 行时，前面有 0 行；位于第 3 行时，前面只有 2 行。之所以再乘 7，是因为每个完整行恰好有 7 个格子。

例如 first = 3、second = 4：

前面有 3 - 1 = 2 行
前两行共有 2 × 7 = 14 个格子
当前格子在第 3 行排第 4
所以总编号为 14 + 4 = 18

再观察每一行产生的编号：

first = 1：(1 - 1) × 7 + second => 1～7
first = 2：(2 - 1) × 7 + second => 8～14
first = 3：(3 - 1) × 7 + second => 15～21
...
first = 7：(7 - 1) × 7 + second => 43～49

前一行的最后一个编号与后一行的第一个编号刚好相邻。例如第一行结束于 7，第二行从 8 开始。因此不同的组合不会得到相同编号，1～49 之间也不会有遗漏。

为什么“编号不重复”就意味着结果均匀

每个编号都恰好由一个有序组合产生：

编号 1  只来自组合 (1, 1)
编号 8  只来自组合 (2, 1)
编号 18 只来自组合 (3, 4)
编号 49 只来自组合 (7, 7)

每个组合出现的概率都是 1/49，而每个编号都只对应其中一个组合，所以每个编号出现的概率也都是 1/49：

49 个等概率组合
        ↓ 一一对应
1～49 这 49 个整数

这里的关键并不是“结果范围恰好从 1 到 49”，而是一一对应。如果多个组合可能得到同一个数字，并且每个数字对应的组合数量不同，结果就不会均匀。例如直接相加时，和为 2 只有 (1, 1) 一种组合，和为 8 却有 7 种组合，所以相加不能产生均匀分布。

这个编号公式不是唯一写法，也可以先生成 0～48：

const num = (rand7() - 1) * 7 + (rand7() - 1);

真正重要的不是背公式，而是让所有等概率组合与目标区间中的整数形成一一映射。

如何判断构造是否覆盖所有整数

以 f(a, b) = (a - 1) × 7 + b 为例，可以按下面的清单判断：

输入组合是否等概率：题目默认两次 rand7() 独立且均匀，因此满足。
组合数量是否足够：共有 7 × 7 = 49 个组合。
不同组合是否产生不同结果：每一行拥有独立的 7 个编号，不会相互重叠。
结果是否连续：各行依次生成 1～7、8～14、……、43～49。
是否无遗漏：连续区间长度为 49，正好等于组合数量。

这种构造本质上是进制编号。两次 RandM() 可以均匀生成 0～M²-1：

const num = (randM() - 1) * M + (randM() - 1);

三次 RandM() 则可以均匀生成 0～M³-1：

const num =
  (randM() - 1) * M * M +
  (randM() - 1) * M +
  (randM() - 1);

判断其他构造时，不能只看最小值和最大值，还要检查是否有重复和遗漏。只要不同等概率组合映射到同一个结果的数量不一致，输出就不是均匀分布。

为什么用 `((num - 1) % 10) + 1`

拒绝 41～49 后，num 均匀分布在 1～40。现在需要把这 40 个等概率状态平均映射到 1～10。

((num - 1) % 10) + 1

可以分为三步：

num - 1：把 1～40 平移为 0～39。
% 10：把 0～39 平均折叠为 0～9，每个结果恰好有 4 个来源。
+ 1：把 0～9 平移为题目要求的 1～10。

最终映射关系为：

1、11、21、31   -> 1
2、12、22、32   -> 2
...
9、19、29、39   -> 9
10、20、30、40  -> 10

每个输出都对应 4 个等概率的原始状态，因此出现概率都是 4/40 = 1/10。

能否直接使用 `num % 10`

不能直接返回：

return num % 10;

因为取模结果是 0～9，会产生 0，却永远不会产生题目要求的 10。

下面的写法可以均匀生成 1～10：

return (num % 10) + 1;

但映射顺序会发生一次轮转：

10、20、30、40  -> 1
1、11、21、31   -> 2
...
9、19、29、39   -> 10

它在概率上没有问题，只是 ((num - 1) % 10) + 1 的编号关系更自然。通用地，将从 1 开始的整数映射到 1～N 可以写成：

((数字 - 1) % N) + 1

JavaScript 实现

/**
 * rand7() 已由题目提供，等概率返回 1～7。
 *
 * @return {number} 1～10 的均匀随机整数
 */
var rand10 = function () {
  while (true) {
    const num = (rand7() - 1) * 7 + rand7();

    if (num <= 40) {
      return ((num - 1) % 10) + 1;
    }
  }
};

这里的 while (true) 不会导致算法永久无法结束：每轮成功概率为 40/49，连续失败的概率会指数下降，最终结束的概率为 1。

代码中的判断顺序不能反过来：只有先确认 num <= 40，才能对它取模并返回；41～49 必须整体拒绝。每次拒绝后需要重新调用两次 rand7()，生成一个新的独立样本。

正确性说明

两次 rand7() 的每个有序组合出现概率都是 1/49，因此 num 在 1～49 上均匀分布。

接受采样后，num 条件均匀分布在 1～40。对任意目标值 k ∈ [1, 10]，恰好有 4 个数经过 ((num - 1) % 10) + 1 映射到 k，所以：

P(rand10() = k) = 4 / 40 = 1 / 10

因此实现满足均匀随机要求。

复杂度

时间复杂度：期望 O(1)。每轮成功概率为 40/49，期望轮数为 49/40。
空间复杂度：O(1)。
期望调用 rand7() 的次数：2 × 49/40 = 2.45 次。

理论上循环次数没有固定上界，但运行很久的概率极低。

可选优化：复用被拒绝的随机空间

基础解法已经足够清晰。若继续追求更少的 rand7() 调用，可以复用上一轮被拒绝的 9 个等概率状态：

var rand10 = function () {
  while (true) {
    let num = (rand7() - 1) * 7 + rand7(); // 1～49
    if (num <= 40) return ((num - 1) % 10) + 1;

    num = (num - 40 - 1) * 7 + rand7(); // 1～63
    if (num <= 60) return ((num - 1) % 10) + 1;

    num = (num - 60 - 1) * 7 + rand7(); // 1～21
    if (num <= 20) return ((num - 1) % 10) + 1;
  }
};

优化版的关键仍然相同：每一步只接受状态数为 10 的整数倍的区间。面试时建议先写基础版本，再根据追问解释复用方案。

常见错误

1. 直接取模

return rand7() % 10 + 1;

它不仅不均匀，而且无法覆盖全部 1～10。

2. 对 1～49 直接模 10

const num = (rand7() - 1) * 7 + rand7();
return ((num - 1) % 10) + 1;

49 不是 10 的整数倍。结果 1～9 各有 5 个来源，而结果 10 只有 4 个来源，因此不均匀。

3. 不平移就直接套用原来的边界

const num = rand7() * 7 + rand7(); // 8～56

这个表达式仍然产生 49 个等概率状态，所以它本身并非不均匀；问题是不能继续沿用针对 [1, 49] 设计的“接受 1～40”和取模公式。如果先将结果减 7，再完成拒绝采样，也可以得到正确答案。为了减少边界换算，通常写成：

const num = (rand7() - 1) * 7 + rand7(); // 1～49

4. 认为随机数调用天然独立

本题默认每次 rand7() 调用相互独立且均匀。若底层随机源不满足这个前提，上述证明不成立。

5. 使用比例缩放

return Math.floor((rand7() * 10) / 7);

单次 rand7() 只有 7 个随机状态，确定性计算最多仍然只能产生 7 种输出。上述写法只能得到 1、2、4、5、7、8、10，无法得到 3、6、9。

6. 直接将两次结果相乘

return rand7() * rand7();

乘法会让不同组合合并到同一个结果，而且合并数量不同。例如 1 只有组合 (1, 1)，而 4 有 (1, 4)、(2, 2)、(4, 1) 三种组合，所以它们的概率分别为 1/49 和 3/49。它也无法覆盖 1～49 中的所有整数。

面试官可能继续追问

1. 为什么两次 `rand7()` 能均匀生成 1～49？

因为两个独立结果构成 49 个等概率有序对，公式为每个有序对建立了到 1～49 的一一映射。考察点是一一映射和独立性。

2. 为什么必须拒绝 41～49？

因为 49 不能被 10 整除，无法让 10 个结果拥有相同数量的来源。考察点是均匀分布的必要条件。

3. 为什么先减 1 再取模？

取模天然产生 0～9，所以先把 1～40 平移到 0～39，取模后再加 1。考察点是区间映射。

4. `while (true)` 会不会死循环？

理论上可能执行任意多轮，但第 n 轮仍未成功的概率为 (9/49)^n，极限为 0，因此几乎必然终止。考察点是期望复杂度与最坏情况的区别。

5. 期望调用多少次 `rand7()`？

每轮成功概率为 40/49，期望轮数是 49/40；每轮调用两次，所以期望调用次数是 49/20 = 2.45。考察点是几何分布。

6. 能否用 `Math.random()`？

不能。题目限制只能使用 rand7()；绕过随机源就失去了考察意义。考察点是约束意识。

7. 如何用 `RandM()` 实现 `RandN()`？

调用 k 次 RandM() 构造 M^k 个等概率状态，使 M^k >= N，然后接受不超过 floor(M^k / N) * N 的部分并取模映射。考察点是方法迁移。

更完整地说，先把每次 RandM() 的结果减 1，将它当成一个 M 进制数位：

x = d(k-1) × M^(k-1) + ... + d1 × M + d0

这样 x 均匀分布在 [0, M^k - 1]。令：

limit = floor(M^k / N) × N

仅接受 x < limit，然后返回 x % N + 1；其余状态重新采样。通常选择满足 M^k >= N 的最小 k，避免无意义地扩大样本空间。

8. 基础版和复用版如何选择？

基础版证明简单、代码可靠；复用版平均调用次数更少，但边界更容易出错。面试应先保证正确，再讨论优化。考察点是工程取舍。

迁移总结

核心关键词：等概率样本空间、一一映射、拒绝采样、取模、期望复杂度。
一句话本质：把 Rand7() 扩展成更大的均匀空间，再截取 10 的整数倍个状态映射到 1～10。
思考链路：7 × 7 = 49 个等概率状态 → 接受 40 个 → 每 4 个映射到一个结果 → 得到 Rand10()。
可迁移场景：用 RandM() 实现 RandN()、随机抽样、哈希到桶的均匀映射、随机算法中的偏差消除。

记忆模板

遇到“用 RandM() 实现 RandN()”时，可以按以下顺序思考：

用多次独立调用构造不少于 N 个等概率状态。
找到不超过状态总数的最大 N 的整数倍。
拒绝多余状态，保证剩余状态可以被平均分组。
通过取模把每组映射到目标区间。
分别说明均匀性、几乎必然终止和期望复杂度。

#470. 用 Rand7() 实现 Rand10()

#题目描述

#面试结论

#题目本质

#解题过程

#为什么这个公式能均匀生成 1～49

#公式是怎样构造出来的

#为什么“编号不重复”就意味着结果均匀

#如何判断构造是否覆盖所有整数

#为什么用 ((num - 1) % 10) + 1

#能否直接使用 num % 10

#JavaScript 实现

#正确性说明

#复杂度

#可选优化：复用被拒绝的随机空间

#常见错误

#1. 直接取模

#2. 对 1～49 直接模 10

#3. 不平移就直接套用原来的边界

#4. 认为随机数调用天然独立

#5. 使用比例缩放

#6. 直接将两次结果相乘

#面试官可能继续追问

#1. 为什么两次 rand7() 能均匀生成 1～49？

#2. 为什么必须拒绝 41～49？

#3. 为什么先减 1 再取模？

#4. while (true) 会不会死循环？

#5. 期望调用多少次 rand7()？

#6. 能否用 Math.random()？

#7. 如何用 RandM() 实现 RandN()？

#8. 基础版和复用版如何选择？

#迁移总结

#记忆模板