难度: Medium
给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。
你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。
每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。
示例 1:
输入: 1 输出: [2]
示例 2:
输入: 2 输出: [2,8]
示例 3:
输入: 3 输出: [3,8,10]
提示:
1 <= n <= 105进阶:
rand7()调用次数的 期望值 是多少 ?rand7() ?运行时间: 89 ms
内存: 18.5 MB
class Solution:
def rand10(self):
"""
:rtype: int
"""
while True:
index = (rand7() - 1) * 7 + rand7()
if(index <= 40): return (index - 1) % 10 + 1
要使用rand7()实现rand10()，关键是如何扩展rand7()生成的范围以覆盖1到10并保持均匀分布。首先，(rand7() - 1)将生成0到6的均匀分布。然后，(rand7() - 1) * 7将生成0, 7, 14, ..., 42的等差序列，这些是7的倍数。再加上另一次rand7()调用，结果为(rand7() - 1) * 7 + rand7()，这可以生成1到49之间的均匀分布的数字。接下来，为了得到1到10的均匀分布，我们只取1到40之间的结果，因为40是最接近49的可以被10整除的数。这样1到40的每个数字都有相同的概率出现。最后，使用(index - 1) % 10 + 1将1到40的数字映射到1到10的范围。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def rand10(self):
\"\"\"
:rtype: int
使用rand7()实现rand10()，通过生成1到49的均匀随机数，然后取其在1到40之间的值，最后映射到1到10。
\"\"\"
while True:
index = (rand7() - 1) * 7 + rand7() # 生成1到49的均匀随机数
if(index <= 40): return (index - 1) % 10 + 1 # 将1到40均匀映射到1到10
选择将(rand7() - 1)与7相乘是为了扩展rand7()生成的范围，同时保持均匀分布。由于(rand7() - 1)生成的是0到6之间的均匀随机整数，乘以7正好可以产生0, 7, 14, ..., 42这些7的倍数。这样再加上一个1到7的随机数，就可以覆盖1到49之间的所有整数，而且每个数出现的概率是相同的，从而保持了随机性和均匀性。
将结果限制在1到40之间而不直接使用1到49的结果进行模运算，是为了确保每个数字在最终输出1到10的映射中出现的概率完全相同，从而保持均匀分布。如果直接从1到49映射到1到10，那么1到9的数字会比10出现的概率稍高（因为49不能被10整除，导致1到9各有5个映射，而10只有4个）。限制在40以内，每个数字映射到1到10的数量都是4个，确保了均匀性。
是的，(rand7() - 1) * 7 + rand7()确实可以均匀覆盖1到49的所有数字。这是因为(rand7() - 1) * 7生成的是0到42之间的7的倍数，每次增加7。然后再通过加上一个1到7的随机数，刚好可以填补这些间隔，从而生成1到49的每一个数字。每个数字生成的概率都是1/49，保持了均匀分布。