> For the complete documentation index, see [llms.txt](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/470.implement-rand10-using-rand7.md).
# 0470. 用 Rand7() 实现 Rand10
### 题目地址(470. 用 Rand7() 实现 Rand10)
### 题目描述
```
已有方法 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，以及求算法期望。求期望[官方题解](https://leetcode-cn.com/problems/implement-rand10-using-rand7/solution/yong-rand7-shi-xian-rand10-by-leetcode-s-qbmd/)写的不错，我就不赘述了。
这里简单讲下尽量减少 rand7 调用的思路。
两次 rand7 生成的 49 个数我们只使用了 10 个，而拒绝了其他 39 个，这其实效率不高。
我们可以利用另外一种生成数字的方式，使得等概率的数更多。比如将第一次 rand7 的结果作为行号，将第二次 rand7 的结果作为列号。那么就可以**等概率生成 49 个数**。为了尽可能少的调用 rand7，我们需要减少拒绝采样的次数。
我们可以使用这 49 个数么？显然不能，因此 49 个数无法等概率映射到 10 个数上。而 40 ，30，20，10 可以。为了尽可能少拒绝采样，我们应该选择 40 。
[官方题解](https://leetcode-cn.com/problems/implement-rand10-using-rand7/solution/yong-rand7-shi-xian-rand10-by-leetcode-s-qbmd/)还提供了一种更加优化的方式，很不错，大家可以参考一下。
### 关键点
* 选择等概率的十个数即可实现 rand10
### 代码
* 语言支持：Python3
Python3 Code:
```python
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)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
