【刷穿 LeetCode】470. 用 Rand7() 实现 Rand10() : k 进制诸位生成 + 拒绝采样-阿里云开发者社区

【刷穿 LeetCode】470. 用 Rand7() 实现 Rand10() : k 进制诸位生成 + 拒绝采样

2022-05-05 101

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【刷穿 LeetCode】470. 用 Rand7() 实现 Rand10() : k 进制诸位生成 + 拒绝采样

网络异常，图片无法展示

题目描述

这是 LeetCode 上的 470. 用 Rand7() 实现 Rand10() ，难度为中等。

Tag : 「位运算」、「数学」

已有方法 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() ?

基本分析

给定一个随机生成 11 ~ 77 的函数，要求实现等概率返回 11 ~ 1010 的函数。

首先需要知道，在输出域上进行定量整体偏移，仍然满足等概率，即要实现 00 ~ 66 随机器，只需要在 rand7 的返回值上进行 -1−1 操作即可。

但输出域的拼接/叠加并不满足等概率。例如 rand7() + rand7() 会产生 [2, 14][2,14] 范围内的数，但每个数并非等概率：

产生 22 的概率为：\frac{1}{7} * \frac{1}{7} = \frac{1}{49}71∗71=491
产生 44 的概率为：\frac{1}{7} * \frac{1}{7} + \frac{1}{7} * \frac{1}{7} + \frac{1}{7} * \frac{1}{7} = \frac{3}{49}71∗71+71∗71+71∗71=493

在 [2, 14][2,14] 这 1313 个数里面，等概率的数值不足 1010 个。

因此，你应该知道「执行两次 rand7() 相加，将 [1, 10][1,10] 范围内的数进行返回，否则一直重试」的做法是错误的。

kk 进制诸位生成 + 拒绝采样

上述做法出现概率分布不均的情况，是因为两次随机值的不同组合「相加」的会出现相同的结果（(1, 3)(1,3)、(2, 2)(2,2)、(3, 1)(3,1) 最终结果均为 44）。

结合每次执行 rand7 都可以看作一次独立事件。我们可以将两次 rand7 的结果看作生成 77 进制的两位。从而实现每个数值都唯一对应了一种随机值的组合（等概率），反之亦然。

举个🌰，设随机执行两次 rand7 得到的结果分别是 44（第一次）、77（第二次），由于我们是要 77 进制的数，因此可以先对 rand7 的执行结果进行 -1−1 操作，将输出域偏移到 [0, 6][0,6]（仍为等概率），即得到 33（第一次）和 66（第二次），最终得到的是数值 (63)_7(63)7，数值 (63)_7(63)7 唯一对应了我们的随机值组合方案，反过来随机值组合方案也唯一对应一个 77 进制的数值。

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

回到本题，执行一次 rand7 只能产生 [0, 6][0,6] 范围内的数值，不足 1010 个；而执行 22 次 rand7 的话则能产生 [0, 48][0,48] 范围内的数值，足够 1010 个，且等概率。

我们只需要判定生成的值是否为题意的 [1, 10][1,10] 即可，如果是的话直接返回，否则一直重试。

代码：

class Solution extends SolBase {
    public int rand10() {
        while (true) {
            int ans = (rand7() - 1) * 7 + (rand7() - 1); // 进制转换
            if (1 <= ans && ans <= 10) return ans;
        }
    }
}
复制代码

时间复杂度：期望复杂度为 O(1)O(1)，最坏情况下为 O(\infty)O(∞)
空间复杂度：O(1)O(1)

进阶

降低对 rand7 的调用次数

我们发现，在上述解法中，范围 [0, 48][0,48] 中，只有 [1, 10][1,10] 范围内的数据会被接受返回，其余情况均被拒绝重试。

为了尽可能少的调用 rand7 方法，我们可以从 [0, 48][0,48] 中取与 [1, 10][1,10] 成倍数关系的数，来进行转换。

我们可以取 [0, 48][0,48] 中的 [1, 40][1,40] 范围内的数来代指 [1, 10][1,10]。

首先在 [0, 48][0,48] 中取 [1, 40][1,40] 仍为等概率，其次形如 x1x1 的数值有 44 个（11、1111、2121、3131），形如 x2x2 的数值有 44 个（22、1212、2222、3232）... 因此最终结果仍为等概率。

代码：

class Solution extends SolBase {
    public int rand10() {
        while (true) {
            int ans = (rand7() - 1) * 7 + (rand7() - 1); // 进制转换
            if (1 <= ans && ans <= 40) return ans % 10 + 1;
        }
    }
}
复制代码