Medium

题目描述

已知有一个 API rand7() 可以生成 [1, 7] 范围内的均匀随机整数，请编写一个函数 rand10() 来生成 [1, 10] 范围内的均匀随机整数。你只能调用 rand7() API，不能调用其他 API。请不要使用语言的内置随机 API。

每个测试用例都有一个内部参数 n，代表测试时调用 rand10() 函数的次数。注意这不是传递给 rand10() 的参数。

示例 1:

输入: n = 1
输出: [2]

示例 2:

输入: n = 2
输出: [2,8]

示例 3:

输入: n = 3
输出: [3,8,10]

约束条件:

  • 1 <= n <= 10^5

进阶:

  • 调用 rand7() 函数的期望次数是多少？
  • 你能否最小化对 rand7() 的调用次数？

解题思路

解题思路

这是一个经典的拒绝采样（Rejection Sampling）问题。我们需要用能生成 1-7 随机数的函数来生成 1-10 的随机数。

核心思想

  1. 构造更大的等概率空间：通过两次调用 rand7() 可以生成 [1, 49] 范围内的随机数
  2. 映射到目标范围：从这 49 个数中取出能被 10 整除的部分（40 个），映射到 [1, 10]
  3. 拒绝采样：如果生成的数不在有效范围内，则重新采样

具体步骤

  • 第一次调用 rand7() 得到 a，第二次调用得到 b
  • 计算 num = (a-1) * 7 + (b-1)，这样可以等概率地生成 [0, 48] 范围的数
  • 如果 num < 40，则返回 num % 10 + 1
  • 否则重新采样（拒绝采样的核心）

优化思路

基础方法每次拒绝 9 个数字，拒绝率为 9/49。可以进一步优化：

  • 当 num >= 40 时，num - 40 在 [0, 8] 范围内
  • 可以再次利用这个范围继续生成随机数，减少浪费

这种方法的期望调用次数约为 2.45 次，相比基础方法的 2.8 次有所改进。

代码实现

class Solution {
public:
    int rand10() {
        while (true) {
            int a = rand7();
            int b = rand7();
            int num = (a - 1) * 7 + (b - 1);
            if (num < 40) {
                return num % 10 + 1;
            }
            
            // 优化：利用 [40, 48] 的 9 个数
            a = num - 40;  // [0, 8]
            b = rand7();
            num = a * 7 + (b - 1);  // [0, 62]
            if (num < 60) {
                return num % 10 + 1;
            }
            
            // 继续优化：利用 [60, 62] 的 3 个数
            a = num - 60;  // [0, 2]
            b = rand7();
            num = a * 7 + (b - 1);  // [0, 20]
            if (num < 20) {
                return num % 10 + 1;
            }
        }
    }
};

class Solution:
    def rand10(self):
        while True:
            a = rand7()
            b = rand7()
            num = (a - 1) * 7 + (b - 1)
            if num < 40:
                return num % 10 + 1
            
            # 优化：利用 [40, 48] 的 9 个数
            a = num - 40  # [0, 8]
            b = rand7()
            num = a * 7 + (b - 1)  # [0, 62]
            if num < 60:
                return num % 10 + 1
            
            # 继续优化：利用 [60, 62] 的 3 个数
            a = num - 60  # [0, 2]
            b = rand7()
            num = a * 7 + (b - 1)  # [0, 20]
            if num < 20:
                return num % 10 + 1

public class Solution : SolBase {
    public int Rand10() {
        while (true) {
            int a = Rand7();
            int b = Rand7();
            int num = (a - 1) * 7 + (b - 1);
            if (num < 40) {
                return num % 10 + 1;
            }
            
            // 优化：利用 [40, 48] 的 9 个数
            a = num - 40;  // [0, 8]
            b = Rand7();
            num = a * 7 + (b - 1);  // [0, 62]
            if (num < 60) {
                return num % 10 + 1;
            }
            
            // 继续优化：利用 [60, 62] 的 3 个数
            a = num - 60;  // [0, 2]
            b = Rand7();
            num = a * 7 + (b - 1);  // [0, 20]
            if (num < 20) {
                return num % 10 + 1;
            }
        }
    }
}

var rand10 = function() {
    while (true) {
        let a = rand7();
        let b = rand7();
        let num = (a - 1) * 7 + (b - 1);
        if (num < 40) {
            return num % 10 + 1;
        }
        
        // 优化：利用 [40, 48] 的 9 个数
        a = num - 40;  // [0, 8]
        b = rand7();
        num = a * 7 + (b - 1);  // [0, 62]
        if (num < 60) {
            return num % 10 + 1;
        }
        
        // 继续优化：利用 [60, 62] 的 3 个数
        a = num - 60;  // [0, 2]
        b = rand7();
        num = a * 7 + (b - 1);  // [0, 20]
        if (num < 20) {
            return num % 10 + 1;
        }
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(1) 平均情况，期望调用 rand7() 约 2.45 次
空间复杂度O(1) 只使用常数额外空间