题目地址(470. 用 Rand7() 实现 Rand10)

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 的随机数，然后映射到 10 。

这显然是不正确的。因此 rand7 只能生成 7 种结果，无法扩展到 10 种结果的随机。因此我们至少需要一种大于 10 的生成结果才能实现 rand10。

由于我们只能使用 rand7 来实现 rand10，因此不妨进行多次 rand10。

那么两次 rand7 可以么？很明显两次 rand7 的结果相乘可以产生 7x7 = 49 种结果，大于 10。因此我们要做的就是从这 49 种结果中找到等概率的 10 种即可

由于生成 2，3，5，7，8，10，14，15，16，20，21，24，28，30，35，42 的概率都是 2/49。因此我们不妨选择2，3，5，7，8，10，14，15，16，20 这十个数。并且将 1 映射到 2， 2 映射到 3 。。。以此类推。

如果两次 rand7 的结果相乘在这十个数中，那么我们就随机生成了一个 1 - 10 的随机数，否则就拒绝采样，重新执行两次 rand7 ，并重复上面过程。

这种算法的正确性在于生成2，3，5，7，8，10，14，15，16，20 是等概率的，并且我们抹去了生成其他数的可能，因此生成这十个数的概率就同为 1 / 10。

题目的进阶是如何尽量少调用 rand7，以及求算法期望。求期望官方题解写的不错，我就不赘述了。

这里简单讲下尽量减少 rand7 调用的思路。

两次 rand7 生成的 49 个数我们只使用了 10 个，而拒绝了其他 39 个，这其实效率不高。

我们可以利用另外一种生成数字的方式，使得等概率的数更多。比如将第一次 rand7 的结果作为行号，将第二次 rand7 的结果作为列号。那么就可以等概率生成 49 个数。为了尽可能少的调用 rand7，我们需要减少拒绝采样的次数。

我们可以使用这 49 个数么？显然不能，因此 49 个数无法等概率映射到 10 个数上。而 40 ，30，20，10 可以。为了尽可能少拒绝采样，我们应该选择 40 。

官方题解还提供了一种更加优化的方式，很不错，大家可以参考一下。

关键点

选择等概率的十个数即可实现 rand10

代码

语言支持：Python3

Python3 Code:

class Solution:
    def rand10(self):
        while True:
            row = rand7()
            col = rand7()
            idx = col + (row - 1) * 7
            if idx <= 40:
                break

        return 1 + (idx - 1)%10

复杂度分析

令 n 为数组长度。

时间复杂度：$O(+\infty)$ 可能会无限拒绝
空间复杂度：$O(1)$

此题解由力扣刷题插件自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。