自学内容网 自学内容网

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. 生成一个1到49之间的随机整数res,通过计算(rand7() - 1) * 7 + rand7()
  2. 如果res大于40,我们将其丢弃并重新生成,直到得到一个40或以下的数。
  3. 将得到的数对10取模,然后加1,得到一个1到10之间的均匀随机整数。

算法流程

开始
rand7 - 1
* 7
+ rand7
res > 40?
重新生成
res % 10
+ 1
返回结果
结束

算法代码

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)!