LeetCode 478. 在圆内随机生成点
题目描述
题意分析
每次返回圆内的一个随机坐标，要求任意区域被选中的概率与它的面积成正比。可以先在以原点为圆心的圆内采样，再加上给定圆心的坐标完成平移。
解法：极坐标采样
核心思路
[!blue]
用极坐标表示点：方向角为 $\theta$，到圆心的距离为 $d$。所有方向对称，所以让 $\theta$ 在 $[0,2\pi)$ 上均匀分布；距离的分布则要由面积推导。
设圆半径为 $R$，距离圆心不超过 $r$ 的区域占总面积的比例为 $\pi r^2/(\pi R^2)=(r/R)^2$，因此必须满足 $P(d\le r)=(r/R)^2$。取均匀随机数 $u\in[0,1)$，令 $d=R\sqrt{u}$，就有 $P(d\le r)=P(u\le(r/R)^2)=(r/R)^2$。
方向角和距离分别使用独立抽样。这样每个圆环获得的概率与面积成正比，同一圆环内各个方向也均匀，得到的点便在整个圆内均匀分布。若直接令 $d=Ru$，相同宽度的内外圆环会获得相同概率，但内圈面积更小，点就会过度集中在圆心附近。
最后转换为直角坐标：
x = xCenter + d * cos(theta)、y = yCenter + d * sin(theta)。平移只改变圆的位置，不改变分布。
解题步骤
- 构造时保存半径
radius和圆心坐标。- 每次调用分别取得两个均匀随机数，一个用于生成方向角，另一个作为面积比例。
- 用
radius * sqrt(u)计算到圆心的距离。- 用正弦、余弦计算相对坐标，再加上圆心并返回两个坐标。
代码实现
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
};
}
}
import (
"math"
"math/rand"
)
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)$，对象状态与返回坐标长度固定。
关键点总结
[!green]
- 随机半径的平方与面积成正比。
- 两个独立随机样本也可能恰好相等，独立不等于数值必须不同。
易错点总结
[!yellow]
- 半径直接乘均匀随机数，会过度采样内圈。
- 角度与距离复用同一个随机量，会让点集中在一条曲线上。
- 漏加圆心偏移，会围绕错误的圆心采样。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 497. 非重叠矩形中的随机点 | 中等 | 同样要求几何区域内均匀采样，原题在离散矩形格点间按点数加权，本题在连续圆面积上均匀。 |
| 470. 用 Rand7() 实现 Rand10() | 中等 | 拒绝采样的均匀性证明相同：保留区域中的每个原等概率位置仍等概率。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！