美文网首页
470. 用 Rand7() 实现 Rand10()

470. 用 Rand7() 实现 Rand10()

作者: 秃头哥编程 | 来源:发表于2021-09-06 00:24 被阅读0次

    2021-09-05 LeetCode每日一题

    链接: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()生成[1, 7]的均匀随机整数,定量整体偏移后,依然满足等概率生成。所以在rand7()生成结果的基础上进行-1操作后生成[0, 6]依然是满足条件的。

    但如果对输出域进行拼接/叠加是不满足等概率生成的。比如两个rand7() + rand7()生成结果的范围是[2, 14],但并不是每个数生成的概率都相等。生成2的概率 = 1/7 * 1/7 + 1/7 * 1/7 = 2/49,生成4的概率 = 1/7 * 1/7 + 1/7 * 1/7 + 1/7 * 1/7 + 1/7 * 1/7 = 4/49。因为1 3和2 2相加都等于4。

    对生成结果进行组合满足等概率生成。比如一个rand7()生成2,一个rand7()生成6,那么组合成26是唯一的。我可以先对生成的结果进行-1操作,然后再进行组合,其实就生成了一个7进制的数。

    根据「进制转换」的相关知识,如果我们存在一个 randK 的函数,对其执行 n 次,我们能够等概率产生 [0, K^n - 1] 范围内的数值

    (1)普通版:在这里我们只需要执行两次rand7()函数,就能等概率生成[0, 48]范围内的数,再把[1, 10]范围的数返回即可。

    (2)进化版:上面的时间复杂度可能是O(1),也可能是O(∞)。为了减少rand7()函数的调用,其实可以对结果等比例进行扩大,这样产生符合条件的数的概率就更大。

    对于[1, 10]范围内的,我们可以扩大到[1, 40],1对应1,11,21,31,2对应2,12,22,32, ....,10对应10,20,30,40。然后对[1,40]范围内的数,只需要对10取余+1即可。

    那么禁不住想问了,每多调用一次rand7(),结果的范围值就会变大,比如调用3次,生成的结果范围在[0, 342],那么等比例扩大到[1, 340],会不会更快呢?我试了下,和调用两次差别不大。然后我尝试调用4次,5次,发现时间是越来越长的。

    (3)rand7 的期望调用次数:在 [0, 48]中我们采纳了 [1, 40] 范围内的数值,即以调用两次为基本单位的话,有 40/49的概率被接受返回(成功)。成功的概率40/49,那么触发成功所需次数(期望次数)为其倒数 49/40 = 1.225 ,每次会调用两次 rand7,因而总的期望调用次数为 1.225 * 2 = 2.45。

    参考链接:https://leetcode-cn.com/problems/implement-rand10-using-rand7/solution/gong-shui-san-xie-k-jin-zhi-zhu-wei-shen-zmd4/

    编码

    普通版

    /**
     * The rand7() API is already defined in the parent class SolBase.
     * public int rand7();
     * @return a random integer in the range 1 to 7
     */
    class Solution extends SolBase {
        public int rand10() {
            while (true) {
                int num = (rand7() - 1) * 7 + (rand7() - 1);
                if (num >= 1 && num <= 10) {
                    return num;
                }
            }
        }
    }
    
    请添加图片描述

    进化版

    /**
     * The rand7() API is already defined in the parent class SolBase.
     * public int rand7();
     * @return a random integer in the range 1 to 7
     */
    class Solution extends SolBase {
        public int rand10() {
            while (true) {
                int num = (rand7() - 1) * 7 + (rand7() - 1);
                if (num >= 1 && num <= 40) {
                    return (num % 10) + 1;
                }
            }
        }
    }
    
    请添加图片描述

    相关文章

      网友评论

          本文标题:470. 用 Rand7() 实现 Rand10()

          本文链接:https://www.haomeiwen.com/subject/aiaswltx.html