0470-用Rand7()实现Rand10()

题目链接

题目描述

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。
不要使用系统的 Math.random() 方法。

示例

示例1：

输入: 3 输出: [8,1,10]

提示

1. rand7 已定义。
2. 传入参数: n 表示 rand10 的调用次数。

   思路

   拒绝采样

   简单地，如果我们直接使用两个 rand7 生成 [2,14] 内的数，此时每个数并非等概率，因此此方法是错误的。
   继续思考，我们的重点就在于找到一组等概率的数，且该组数据的数量大于等于10，我们可以考虑一个七进制数：
   我们调用两次 rand7 ，可以得到一个两位的七进制数，如，我们得到两个数字 2 、3，那么可以得到一个七进制数 12 （每个数字都减一）。
   通过此方法可以得到一个 [0,48] 范围内的数，且满足等概率。
   我们取 [1,10] 内的数即可，但这样又会导致拒绝率过高，进一步优化，取 [1,40] 内的数并取模。
   调用次数：

   进阶

   进一步思考减少 rand7 调用次数：
   在上述方法中每次会拒绝 [41,49] 内的数，然而此范围内的数也满足等概率，因此我们可以想办法将这些数利用起来：
   我们再调用一次 rand7 便可以得到 [1,63] 内的数，我们接受 [1,60] ，剩下的数同理， 得到 [1,21] 的数，此时拒绝域只有 [1] ，我们再重复一开始的操作。
   调用次数：

   题解

   ```cpp // The rand7() API is already defined for you. // int rand7(); // @return a random integer in the range 1 to 7

class Solution { public: int rand10() { while (true) { int ans = (rand7() - 1) 7 + (rand7() - 1); if (ans >= 1 && ans <= 40) { return ans % 10 + 1; } ans = (ans - 40 - 1) 7 + (rand7() - 1); if (ans >= 1 && ans <= 60) { return ans % 10 + 1; } ans = (ans - 60 - 1) * 7 + (rand7() - 1); if (ans >= 1 && ans <= 20) { return ans % 10 + 1; } } } }; ```

复杂度分析

• 时间复杂度：，但最坏情况为 ，即一直被拒绝。
• 空间复杂度：