470. 用 Rand7() 实现 Rand10()

柔光的暖阳◎ 2022-09-10 06:22 103阅读 0赞

#### 2021-09-05 LeetCode每日一题 ####

链接：[https://leetcode-cn.com/problems/implement-rand10-using-rand7/][https_leetcode-cn.com_problems_implement-rand10-using-rand7]

标签：**数学、拒绝采样、概率与统计、随机化**

> 题目

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

不要使用系统的 Math.random() 方法。

示例 1:

输入: 1
    输出: [7]

示例 2:

输入: 2
    输出: [8,4]

示例 3:

输入: 3
    输出: [8,1,10]

提示:

*  rand7 已定义。
 *  传入参数: n 表示 rand10 的调用次数。

进阶:

*  rand7()调用次数的 期望值 是多少 ?
 *  你能否尽量少调用 rand7() ?

> 分析

题目需要均匀随机整数，所以需要确保**生成每个数的概率是相同的**。

`rand7()`生成\[1, 7\]的均匀随机整数，定量整体偏移后，依然满足等概率生成。所以在`rand7()`生成结果的基础上进行-1操作后生成\[0, 6\]依然是满足条件的。

但如果**对输出域进行拼接/叠加是不满足等概率生成**的。比如两个`rand7() + rand7()`生成结果的范围是\[2, 14\]，但并不是每个数生成的概率都相等。生成2的概率 = 1/7 \* 1/7 + 1/7 \* 1/7 = 2/49，生成4的概率 = 1/7 \* 1/7 + 1/7 \* 1/7 + 1/7 \* 1/7 + 1/7 \* 1/7 = 4/49。因为1 3和2 2相加都等于4。

对生成结果进行组合满足等概率生成。比如一个`rand7()`生成2，一个`rand7()`生成6，那么组合成26是唯一的。我可以先对生成的结果进行-1操作，然后再进行组合，其实就生成了一个7进制的数。

根据「进制转换」的相关知识，**如果我们存在一个 randK 的函数，对其执行 n 次，我们能够等概率产生 \[0, K^n - 1\] 范围内的数值**。

（1）**普通版**：在这里我们只需要执行两次`rand7()`函数，就能等概率生成\[0, 48\]范围内的数，再把\[1, 10\]范围的数返回即可。

（2）**进化版**：上面的时间复杂度可能是O(1)，也可能是O(∞)。为了减少`rand7()`函数的调用，其实可以对结果等比例进行扩大，这样产生符合条件的数的概率就更大。

对于\[1, 10\]范围内的，我们可以扩大到\[1, 40\]，1对应1,11,21,31，2对应2,12,22,32， …，10对应10,20,30,40。然后对\[1,40\]范围内的数，只需要对10取余+1即可。

那么禁不住想问了，每多调用一次`rand7()`，结果的范围值就会变大，比如调用3次，生成的结果范围在\[0, 342\]，那么等比例扩大到\[1, 340\]，会不会更快呢？我试了下，和调用两次差别不大。然后我尝试调用4次，5次，发现时间是越来越长的。

（3）`rand7` 的期望调用次数：在 \[0, 48\]中我们采纳了 \[1, 40\] 范围内的数值，即以调用两次为基本单位的话，有 40/49的概率被接受返回（成功）。成功的概率40/49，那么触发成功所需次数（期望次数）为其倒数 49/40 = 1.225 ，每次会调用两次 `rand7`，因而总的期望调用次数为 1.225 \* 2 = 2.45。

参考链接：https://leetcode-cn.com/problems/implement-rand10-using-rand7/solution/gong-shui-san-xie-k-jin-zhi-zhu-wei-shen-zmd4/

> 编码

**普通版**：

/** * The rand7() API is already defined in the parent class SolBase. * public int rand7(); * @return a random integer in the range 1 to 7 */
    class Solution extends SolBase { 
        public int rand10() { 
            while (true) { 
                int num = (rand7() - 1) * 7 + (rand7() - 1);
                if (num >= 1 && num <= 10) { 
                    return num;
                }
            }
        }
    }

![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56eD5aS05ZOl57yW56iL_size_20_color_FFFFFF_t_70_g_se_x_16]

**进化版**：

/** * The rand7() API is already defined in the parent class SolBase. * public int rand7(); * @return a random integer in the range 1 to 7 */
    class Solution extends SolBase { 
        public int rand10() { 
            while (true) { 
                int num = (rand7() - 1) * 7 + (rand7() - 1);
                if (num >= 1 && num <= 40) { 
                    return (num % 10) + 1;
                }
            }
        }
    }

![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56eD5aS05ZOl57yW56iL_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[https_leetcode-cn.com_problems_implement-rand10-using-rand7]: https://leetcode-cn.com/problems/implement-rand10-using-rand7/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56eD5aS05ZOl57yW56iL_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/7ecff73b0361440f85bbfb9d11a1397d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56eD5aS05ZOl57yW56iL_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/7ac43e0aff30434dbbe1ef4aebd56bd5.png