0470. Implement Rand10() Using Rand7() ====================================== 题目信息 -------- :题号: 0470 :难度: Medium :主题: 随机接口、均匀分布、取值范围、仅调用 ``rand7`` :原题: `LeetCode 0470 `_ :重点: ``rand7`` 均匀返回 1 至 7、``rand10`` 必须均匀返回 1 至 10、不能调用其他随机函数 题目重述 -------- 平台提供 ``rand7()``,每次调用都会以相同概率返回整数 ``1..7`` 中的一个值。使用这个接口实现 ``rand10()``,使每次调用都返回 ``1..10`` 中的一个整数,并且十个结果的概率完全相同。 实现只能通过调用 ``rand7()`` 获得随机性,不能使用系统随机函数或预先固定的结果序列。单次调用允许使用不固定次数的 ``rand7()``,但必须最终返回合法范围内的值。判题会重复调用 ``rand10()`` 检查结果范围和统计分布。 自建示例 -------- 单次调用的输出范围: .. code-block:: text 调用:rand10() 输出:1 至 10 中任意一个整数 解释:某一次具体返回值不可预先确定,但不能返回 0、11 或其他范围外数值。 重复调用的分布要求: .. code-block:: text 调用:大量重复执行 rand10() 输出:每次均位于 1..10 解释:长期统计中十个整数各自的理论概率都应为 1/10,不能让部分数字因映射方式不同而更常出现。 先生成 1..49,再拒绝多余结果 ---------------------------- 两次 ``rand7`` 可以把一对结果映射成 ``(row - 1) * 7 + column``,从而均匀生成 1 到 49。只保留其中的 1 到 40,这 40 个结果可以完整地分成 10 组,每组 4 个,再用模运算映射到 1 到 10;落在 41 到 49 的结果直接重试。 拒绝发生时不会偏向任何保留结果,因为下一轮仍从完整的均匀 1..49 重新抽取。循环次数是不固定的,但最终返回必然位于目标范围且十个值概率相同。 C++ 实现 -------- .. code-block:: cpp // int rand7(); 由题目提供 class Solution { public: int rand10() { int value = 0; do { int row = rand7(); int column = rand7(); value = (row - 1) * 7 + column; } while (value > 40); return (value - 1) % 10 + 1; } }; 代码分析 -------- 每个二维结果 ``(row,column)`` 的概率都是 ``1/49``,接受 1..40 后每个目标数字对应 4 个等概率结果,概率均为 ``4/49`` 再除以接受概率 ``40/49``,得到 ``1/10``。单次调用期望调用 ``rand7`` 的次数为常数,额外空间复杂度为 ``O(1)``。