LeetCode 470. 用 Rand7() 实现 Rand10()

Categories:

题目描述
思路分析
1. 解法一：拒绝采样（推荐）
相似题目

题目描述

✅ 470. 用 Rand7() 实现 Rand10()

思路分析

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

核心思路：

用两次 rand7() 构造一个 1~49 的均匀分布，再从中取均匀的 1~10。

推导过程：

rand7() 产生 1~7 等概率，将其视为行列： idx = (rand7() - 1) * 7 + rand7()，产生 1~49，每个值概率均等（1/49）

取 1~40 的部分：40 = 4 × 10，对 40 取模加 1 恰好得到均匀的 1~10

idx % 10 + 1（注意 40 % 10 = 0，+1 = 1；其余同理）

若 idx > 40（即 41~49，共 9 种情况），拒绝本次采样，重新调用

关键：拒绝的概率为 9/49 ≈ 18.4%，期望调用次数 = 2 / (40/49) ≈ 2.45 次。

复杂度分析：

时间复杂度：期望 O(1)，每轮成功概率 40/49，几何分布期望有限

空间复杂度：O(1)

class Solution extends SolBase {
    public int rand10() {
        while (true) {
            // 生成 1~49 的均匀分布
            int row = rand7();
            int col = rand7();
            int idx = (row - 1) * 7 + col;
            // 只取 1~40，mod 10 + 1 得到均匀的 1~10
            if (idx <= 40) {
                return idx % 10 + 1;
            }
            // 超出范围则拒绝，重新采样
        }
    }
}

func rand10() int {
    for {
        // 生成 1~49 的均匀分布
        row := rand7()
        col := rand7()
        idx := (row-1)*7 + col
        // 只取 1~40，mod 10 + 1 得到均匀的 1~10
        if idx <= 40 {
            return idx%10 + 1
        }
        // 超出范围则拒绝，重新采样
    }
}

相似题目

题目	难度	考察点
478. 在圆内随机生成点	中等	拒绝采样、概率
528. 按权重随机选择	中等	前缀和、概率分布
384. 打乱数组	中等	Fisher-Yates 洗牌算法
380. O(1) 时间插入、删除和获取随机元素	中等	随机化、哈希表
519. 随机翻转矩阵	中等	随机化、映射

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/78229822