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 |
原文地址：https://blog.csdn.net/qq_51350957/article/details/142341275
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！