Leetcode 470. 用 Rand7() 实现 Rand10()
Leetcode 470. 用 Rand7() 实现 Rand10()
已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。
不要使用系统的 Math.random() 方法。
示例 1:
输入: 1
输出: [7]
示例 2:
输入: 2
输出: [8,4]
示例 3:
输入: 3
输出: [8,1,10]
目录
- 题目分析
- 算法介绍
- 算法步骤
- 算法流程
- 算法代码
- 算法分析
- 相似题目
题目分析
这是一个关于生成均匀随机数的问题。题目要求实现一个rand10()函数，该函数返回一个1到10之间的均匀随机整数。这个问题可以通过调用一个已知的rand7()函数来解决，rand7()函数返回一个1到7之间的均匀随机整数。
算法介绍
要生成1到10之间的均匀随机整数，我们可以利用rand7()函数生成一个1到49之间的随机整数，然后将其映射到1到10的范围内。由于49不能被10整除，我们需要丢弃一些不均匀的结果并重新生成。
算法步骤
- 生成一个1到49之间的随机整数
res，通过计算(rand7() - 1) * 7 + rand7()。 - 如果
res大于40，我们将其丢弃并重新生成，直到得到一个40或以下的数。 - 将得到的数对10取模，然后加1，得到一个1到10之间的均匀随机整数。
算法流程
算法代码
class Solution {
public:int rand10() {int res = (rand7()-1)*7 + rand7();;while(res > 40)res = (rand7()-1)*7 + rand7();return res % 10 + 1;}
};
算法分析
- 时间复杂度：最坏情况下，我们需要多次调用
rand7()来生成一个有效的随机数，因此时间复杂度取决于生成有效随机数所需的平均调用次数。 - 空间复杂度：O(1)，因为该算法只使用了有限的额外空间。
相似题目
| 题目 | 链接 |
|---|---|
| rand7()实现rand10() | LeetCode 470 |