数组与哈希中等1 种解法

#470用 Rand7() 实现 Rand10()

只调用等概率返回 1 到 7 的 rand7()，实现等概率返回 1 到 10 的 rand10()。

#数学#拒绝采样#随机化

解题主线

(rand7() - 1) × 7 + rand7() 可把两个独立样本映射为等概率的 1..49。

只接受 1..40，再映射为 (sample - 1) % 10 + 1；40 个状态可均匀分成十组。

41..49 必须拒绝并重采样，否则十个结果获得的前像数量不同。

解法 1：49 映射 40 的拒绝采样

用两次 rand7 生成 1..49 的均匀样本，拒绝末尾 9 个状态，将前 40 个状态均匀折叠到 1..10。

时间复杂度

期望 O(1)，每轮接受概率为 40/49

空间复杂度

O(1)

470. 用 Rand7() 实现 Rand10() · 49 映射 40 的拒绝采样

java

import java.util.Objects;
import java.util.random.RandomGenerator;

class SolBase {
    private final RandomGenerator random;

    SolBase() {
        this(RandomGenerator.getDefault());
    }

    SolBase(RandomGenerator random) {
        this.random = Objects.requireNonNull(random);
    }

    protected int rand7() {
        return random.nextInt(1, 8);
    }
}

final class Solution extends SolBase {
    public int rand10() {
        while (true) {
            int sample = (rand7() - 1) * 7 + rand7();
            if (sample <= 40) {
                return (sample - 1) % 10 + 1;
            }
        }
    }
}

用两次 rand7 生成 1..49 的均匀样本，拒绝末尾 9 个状态，将前 40 个状态均匀折叠到 1..10。

LeetCode 提交时平台已提供 SolBase，只需提交 Solution；这里补出一个严格返回 1..7 的 Java 21 SolBase，便于独立理解和编译。

边界与易错点

rand7 契约是闭区间 [1, 7]；旧私有实现 nextInt(7) 实际返回 [0, 6]，既覆盖了父类 API 又破坏均匀映射。
两次 rand7 调用必须是独立等概率样本。
不要用 rand49 % 10 + 1 表达映射边界；(sample - 1) % 10 + 1 更直接地把 1 映射到 1。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/medium/Q470_rand10.java