LeetCode 478. 在圆内随机生成点

2022-04-21 HGNULB 约 8 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 478. 在圆内随机生成点

题意分析

构造函数给定一个圆的半径和圆心坐标，之后每次调用都要返回该圆内部（含边界）的一个点。要求是均匀随机：圆内任意两块面积相等的区域，被采样到的概率必须相等。

「均匀」是本题唯一的难点，也是唯一会被判错的地方。判题不是逐次比对，而是统计大量采样的分布，所以任何在概率上有偏的写法都会失败，哪怕每个点都确实落在圆内。

唯一的随机源是语言标准库提供的均匀随机实数生成器，它只能给出区间 $[0, 1)$ 上的均匀值。所有其他分布都必须从它变换出来，这一点决定了解法的形态。

约束上半径和圆心坐标都是浮点数，调用次数在三万次量级，所以单次采样必须是常数级的、且最好没有循环。边界方面圆心可以是负坐标，返回的点也允许落在圆周上。

解法：极坐标采样

核心思路

最容易想到的写法是拒绝采样：在包住圆的正方形里均匀取一个点，如果落在圆外就重新取。它是正确的，因为正方形内均匀采样限制到圆内仍然均匀。代价是期望调用次数为 $4 / \pi \approx 1.27$ 次，有一个不确定的循环。

想去掉循环，自然的方向是换用极坐标：先随机一个方向角，再随机一个到圆心的距离。方向角在 $[0, 2\pi)$ 上均匀取显然没问题，因为圆关于圆心旋转对称，任何方向都不该被偏爱。

问题出在距离上。如果让距离在 $[0, R]$ 上均匀，就错了。原因是极坐标下的面积微元是 $r \, \mathrm{d}r \, \mathrm{d}\theta$ 而不是 $\mathrm{d}r \, \mathrm{d}\theta$：同样宽度的一圈环带，半径越大，面积越大。距离均匀意味着每一圈环带被分到相同的概率，而外圈的面积远大于内圈，于是圆心附近被严重过采样。

正确的做法是让距离的平方均匀。设点到圆心的距离为 $d$，落在半径 $d$ 的同心圆内的概率应当等于面积之比 $\pi d^2 / \pi R^2 = (d / R)^2$。也就是说 $d$ 的累积分布函数是 $F(d) = (d / R)^2$。用逆变换采样：取 $u$ 在 $[0, 1)$ 上均匀，令 $F(d) = u$ 解得 $d = R \sqrt{u}$。

于是得到本题的不变量：角度在 $[0, 2\pi)$ 上均匀，距离取 $R \sqrt{u}$，两者独立。此时联合分布恰好抵消掉极坐标的雅可比因子 $r$，映射回直角坐标就是圆内的均匀分布。最后加上圆心偏移即可，整个过程无循环、常数时间。

解题步骤

构造函数只做一件事：把半径和圆心坐标存下来。它们在整个对象生命周期内不变，没有任何可以预处理的结构。

每次采样先取角度：从 $[0, 1)$ 的均匀随机数乘以 $2\pi$，得到 $[0, 2\pi)$ 上的均匀角。用左闭右开的区间是刻意的，$0$ 与 $2\pi$ 表示同一方向，闭区间会让这个方向的概率翻倍。

再取一个独立的均匀随机数 $u$ 作为「面积比例」，距离取 $R\sqrt{u}$。可以这样理解 $u$ 的含义：它代表采样点所在同心圆占整个圆的面积份额，面积份额均匀正是均匀分布的定义。

两个随机数必须是两次独立调用。若复用同一个值，采样点会全部落在一条螺旋线上，看似在圆内，实际是零面积集合。

用余弦和正弦把极坐标转成相对圆心的偏移，再分别加上圆心横纵坐标。三角函数在这里只是坐标变换，不影响分布。

返回长度为 2 的数组。整个过程没有循环、没有重试，每次调用的代价固定。

以 radius = 2、圆心 (0, 0)，随机源先后给出 0.25 和 0.25 走一遍：第一个随机数用于角度，$\theta = 0.25 \times 2\pi = \pi / 2$。第二个随机数是 $u = 0.25$，于是距离 $d = 2 \times \sqrt{0.25} = 2 \times 0.5 = 1$。转直角坐标：$x = 0 + 1 \times \cos(\pi/2) = 0$，$y = 0 + 1 \times \sin(\pi/2) = 1$，返回 [0, 1]。

检查这个结果的合理性：$u = 0.25$ 意味着该点应当落在「占总面积四分之一」的同心圆边界上。半径为 2 的圆面积是 $4\pi$，其四分之一是 $\pi$，对应的同心圆半径正是 1，与算出的距离吻合。

再对照错误写法：若把距离直接取成 $R \times u = 2 \times 0.25 = 0.5$，点会落在 [0, 0.5]。半径 0.5 的同心圆只占总面积的 $0.25 / 4 = 6.25\%$，却分到了 25% 的概率，圆心附近被过采样四倍——这就是「半径均匀」错在哪里的量化说明。

换圆心也不影响这套推导：若圆心是 (10, -5)、其余不变，返回的是 [10, -4]，平移只是给每个样本加同一个常量偏移，分布形状不变。

代码实现

class Solution {
    // 角度可以在 [0, 2π) 上均匀采样，方向天然均匀。
    private final double radius;
    private final double xCenter;
    private final double yCenter;

    public Solution(double radius, double x_center, double y_center) {
        this.radius = radius;
        this.xCenter = x_center;
        this.yCenter = y_center;
    }

    public double[] randPoint() {
        java.util.concurrent.ThreadLocalRandom random =
                java.util.concurrent.ThreadLocalRandom.current();
        double angle = random.nextDouble(2.0 * Math.PI);
        double distance = radius * Math.sqrt(random.nextDouble());
        double x = xCenter + distance * Math.cos(angle);
        double y = yCenter + distance * Math.sin(angle);
        return new double[] {x, y};
    }
}

type Solution struct {
    // 角度可以在 [0, 2π) 上均匀采样，方向天然均匀。
    radius float64
    x      float64
    y      float64
}

func Constructor(radius float64, xCenter float64, yCenter float64) Solution {
    return Solution{radius: radius, x: xCenter, y: yCenter}
}

func (s *Solution) RandPoint() []float64 {
    angle := rand.Float64() * 2.0 * math.Pi
    distance := s.radius * math.Sqrt(rand.Float64())
    x := s.x + distance*math.Cos(angle)
    y := s.y + distance*math.Sin(angle)
    return []float64{x, y}
}

复杂度分析

时间复杂度：$O(1)$，单次采样固定调用两次随机数、一次开方和两次三角函数，没有循环也没有重试，因此代价与半径、圆心和调用次数都无关。

空间复杂度：$O(1)$，对象里只存三个浮点字段，采样过程只用几个局部变量，返回的是长度固定为 2 的数组。

关键点总结

几何均匀采样的判据是面积（或体积），不是坐标参数。凡是换到极坐标、球坐标的采样题，都要先问一句「面积微元里有没有多出来的因子」。

逆变换采样是把均匀随机数改造成任意分布的通用工具：写出目标累积分布函数，令它等于 $u$，反解出变量。本题的 $d = R\sqrt{u}$ 就是这么来的。

平方根出现在这里不是技巧而是必然。二维面积随半径平方增长，所以从面积份额还原半径必须开一次方；同理三维球体采样要开立方根。

多个随机量必须各自独立取样，共用同一个随机值会把二维分布塌缩成一维曲线，这类错误在肉眼检查时很难发现。

面试视角：先给出拒绝采样作为无脑正确的基线，说明它的期望重试次数是 $4/\pi$，再引出极坐标的常数时间解法，并主动指出「半径均匀是错的」以及为什么。能把 $\sqrt{u}$ 的来历用面积比例讲明白，是这道题真正的得分点；若追问如何自测，答「统计落在内外两个等面积环带的样本数是否接近」即可。

易错点总结

错误写法：距离取 $R \times u$ 而不是 $R\sqrt{u}$。半径为 2 的圆 → 半径 1 以内的区域只占四分之一面积，却接收了一半样本，分布检验直接判错。

错误写法：角度和距离复用同一个随机数。任意圆 → 所有样本满足 $d = R\sqrt{\theta / 2\pi}$，全部落在一条螺旋线上，虽然点都在圆内，但覆盖的面积为零。

错误写法：先在正方形里取点做拒绝采样，却把判定写成「横纵坐标各自在半径范围内」。任意圆 → 实际接受的是整个正方形，角落里的点也被返回，落到了圆外。

错误写法：拒绝采样时用「不合格就把坐标截断到边界」代替重新采样。任意圆 → 圆周上会堆积起本应属于四角的概率质量，边界被严重过采样。

错误写法：忘记加圆心偏移，直接返回极坐标转换出的相对坐标。圆心为 (10, -5) → 所有点都围绕原点分布，全部落在目标圆之外。

错误写法：角度范围取成 $[0, 2\pi]$ 闭区间，或用 $[0, \pi)$ 再随机决定正负号。前者让 0 方向概率翻倍，后者若符号处理不当会让上下半圆概率失衡。

错误写法：把随机数生成器放在构造函数里只创建一次种子，却在多线程环境下共享同一个非线程安全实例。高频调用 → 内部状态竞争，产生的序列不再均匀甚至重复。

错误写法：为「保证在圆内」而对算出的距离再做一次缩放，比如乘以 0.999 或与 $R$ 取最小值。任意圆 → 靠近圆周的一圈概率被人为削掉，分布不再均匀。

相似题目

题目	难度	考察点
470. 用 Rand7() 实现 Rand10()	中等	离散版拒绝采样，靠丢弃多余状态换取等概率
497. 非重叠矩形中的随机点	中等	先按面积加权选矩形，再在矩形内均匀取整点
528. 按权重随机选择	中等	前缀和加二分实现离散逆变换采样
398. 随机数索引	中等	蓄水池抽样，在流式数据上保持等概率
382. 链表随机节点	中等	长度未知时用蓄水池抽样，只扫一遍且不额外占空间
384. 打乱数组	中等	Fisher-Yates 洗牌，交换范围写错就不再是等概率排列