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() 检查结果范围和统计分布。

自建示例

单次调用的输出范围:

调用:rand10()
输出:1 至 10 中任意一个整数
解释:某一次具体返回值不可预先确定,但不能返回 0、11 或其他范围外数值。

重复调用的分布要求:

调用:大量重复执行 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++ 实现

// 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)。