LeetCode 470 用 Rand7() 实现 Rand10()：python3 题解

目录

• 1. 题目理解
  
  
  
  • 什么是“均匀随机”？
    
  
  
• 2. 为什么不能直接用数学公式？
  
• 3. 核心解法：拒绝采样 (Rejection Sampling)
  
  
  
  • 思路推导
    
  • 解法一：标准拒绝采样（推荐）
    
    
    
    • 复杂度分析
      
    
    
  
  
• 4. 进阶优化：减少 rand7() 调用次数
  
  
  
  • 优化思路
    
  • 解法二：优化版代码
    
  
  
• 5. 总结与对比
  

1. 题目理解

目标：实现一个函数 rand10()，返回 1 到 10 之间的均匀随机整数。
限制：只能使用给定的 rand7() 函数，它返回 1 到 7 之间的均匀随机整数。
核心要求：均匀分布。这意味着生成 1、2、...、10 的概率必须完全相等，都是 \(1/10\)。
什么是“均匀随机”？

如果 rand10() 是均匀的，那么运行很多次后，数字 1 出现的次数应该约等于数字 10 出现的次数。如果某个数字出现的概率偏高，那就不是均匀随机。
2. 为什么不能直接用数学公式？

以下方法的思路相对直接，初学者容易直接想到，但它们都是错误的：

• 错误思路 1：取模
  1. return rand7() % 10 + 1

  复制代码
  原因：rand7() 只能生成 1-7。1%10 是 1，7%10 是 7，永远生成不了 8、9、10。
  
• 错误思路 2：相加
  1. return (rand7() + rand7()) % 10 + 1

  复制代码
  原因：两个随机数相加，结果不是均匀分布的。
  例如：和为 2 只有 (1,1) 一种情况；但和为 8 有 (1,7), (2,6)...(7,1) 七种情况。8 出现的概率远大于 2。这违反了均匀性。
  

3. 核心解法：拒绝采样 (Rejection Sampling)

要生成均匀随机数，最可靠的方法是构造一个更大的均匀空间，然后从中“截取”我们需要的部分。
思路推导

• 扩大样本空间：
  调用两次 rand7()，我们可以得到一个二维坐标 \((a, b)\)，其中 \(a, b \in [1, 7]\)。
  这就像掷两个 7 面的骰子。总共有 \(7 \times 7 = 49\) 种可能的组合。
  由于 rand7() 是均匀的，这 49 种组合中，每一种出现的概率都是 \(1/49\)。
  
• 映射到一维：
  我们可以把这 49 种组合映射到数字 1 到 49。
  公式：idx = (a - 1) * 7 + b
  
  
  
  • a - 1 的范围是 0 到 6。
    
  • (a - 1) * 7 的范围是 0, 7, 14, ..., 42。
    
  • 加上 b (1 到 7) 后，idx 的范围正好是 1 到 49。
    
  • 且 1 到 49 中每个数字出现的概率相等。
    
  
  
• 拒绝采样：
  我们需要 1 到 10 的均匀分布。
  49 不能被 10 整除。如果我们直接把 1-49 映射到 1-10，会导致某些数字概率偏高。
  策略：找到 49 以内最大的、能被 10 整除的数，即 40。
  
  
  
  • 如果生成的 idx 在 1 到 40 之间：我们接受它，并将其映射到 1-10。
    
  • 如果生成的 idx 在 41 到 49 之间：我们拒绝它（丢弃），重新生成两个新的 rand7()。
    
  
  
• 映射结果：
  对于接受的 idx (1-40)，使用公式 (idx - 1) % 10 + 1 即可得到 1-10。
  
  
  
  • 1 -> 1, 11 -> 1, 21 -> 1, 31 -> 1 (共 4 次)
    
  • 10 -> 10, 20 -> 10, 30 -> 10, 40 -> 10 (共 4 次)
    
  • 每个数字被选中的概率完全相等。
    
  
  

解法一：标准拒绝采样（推荐）

这是最清晰、最标准的面试解法。
[code]# The rand7() API is already defined for you.# def rand7():# @return a random integer in the range 1 to 7class Solution:    def rand10(self):        """        :rtype: int        """        while True:            # 1. 调用两次 rand7()，生成两个独立的随机数 a 和 b            a = rand7()            b = rand7()                        # 2. 将二维坐标 (a, b) 映射为一维数字 idx，范围是 [1, 49]            # 解释：(a-1)*7 产生 0, 7, 14...42            # 加上 b (1-7) 后，产生 1 到 49 的均匀分布            idx = (a - 1) * 7 + b                        # 3. 拒绝采样            # 我们只保留 1 到 40 的数字，因为 40 是 10 的倍数            # 41 到 49 的数字会被丢弃，重新循环生成            if idx