LeetCode-Go 题解 478：Generate Random Point in a Circle 圆内均匀随机取点

LeetCode-Go 题解 478：Generate Random Point in a Circle 圆内均匀随机取点

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文基于 LeetCode-Go 仓库中 0478.Generate-Random-Point-in-a-Circle 题目文档，完整剖析 LeetCode 478「Generate Random Point in a Circle」这道经典的均匀随机采样题：给定圆的半径与圆心坐标，实现一个randPoint函数，在圆内（含圆周）产生均匀分布的随机点。读完本文，你将掌握拒绝采样（Rejection Sampling）与极坐标（Polar Coordinates）两种取点算法的数学原理与 Go 实现差异，并了解本仓库题解的单元测试与覆盖率验证方式，可直接复用到任意「在几何区域中均匀采样」的场景。

题目背景与输入输出约定

原题描述

给定圆的半径和圆心的 x、y 坐标，编写一个函数randPoint，该函数在圆中生成一个均匀随机点。原题给出了四条关键说明：

1. 输入和输出值都是浮点数；
2. 圆的半径和圆心的 x、y 坐标通过类构造函数传入；
3. 圆周上的点也认为在圆中；
4. randPoint返回一个包含 x 坐标和 y 坐标的大小为 2 的数组，顺序为先 x 后 y。

输入语法说明

LeetCode 的输入由两个列表组成：被调用的子程序及其参数。Solution的构造函数接收三个参数——半径、圆心 x 坐标、圆心 y 坐标；randPoint无参数。参数即使为空也会用列表包裹，例如：

Input: ["Solution","randPoint","randPoint","randPoint"] [[1,0,0],[],[],[]] Output: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]

第二个示例将半径放大到 10、圆心移到(5, -7.5)：

Input: ["Solution","randPoint","randPoint","randPoint"] [[10,5,-7.5],[],[],[]] Output: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]

由于每次输出都是随机结果，原题并不校验具体数值，只要满足均匀分布与「在圆内」即可。

核心数学约束

圆内任意一点必然满足圆的定义方程：

(x-a)² + (y-b)² ≤ R²

其中(a, b)是圆心坐标，R是半径。题目要求「均匀随机」，意味着圆内每一小块面积被命中的概率应当与它的面积成正比——这是本题最容易踩坑的地方，下文会重点对比两种算法在均匀性上的差异。

解题思路一：拒绝采样（本题解采用）

仓库题解（见 核心实现源码）采用的思路如下：

1. 先假设圆心在 (0,0)：这样便于计算，最终输出坐标时整体加上圆心偏移量即可；
2. 用rand.Float64()产生[0.0, 1.0)区间的浮点数，构造-R ≤ 2 * R * rand() - R < R的横纵坐标候选点；
3. 判断候选点是否满足x² + y² ≤ R²；满足则说明点在圆内，返回；不满足则重新采样，直到命中为止。

这就是经典的拒绝采样：先在一个包含圆的外接正方形内均匀撒点，再把落在圆外的点丢弃。从期望上看，正方形面积为(2R)² = 4R²，圆面积为πR²，因此每次采样被接受的概率为π/4 ≈ 78.5%，平均约 1.27 次即可得到一个有效点，效率完全可接受。

关键代码

func (this *Solution) RandPoint() []float64 { for { rx := 2*rand.Float64() - 1.0 ry := 2*rand.Float64() - 1.0 x := this.r * rx y := this.r * ry if x*x+y*y <= this.r*this.r { return []float64{x + this.x, y + this.y} } } }

几点细节值得注意：

• 2*rand.Float64() - 1.0将[0,1)映射到[-1,1)，再乘以半径this.r得到以原点为中心、边长为2R的正方形内的候选坐标；
• 判定条件x*x+y*y <= this.r*this.r用的是平方比较而非math.Sqrt，既避免了开方带来的浮点开销，也精确满足了「圆周上的点也算在圆内」的要求；
• 命中后将(x, y)加上圆心偏移(this.x, this.y)再返回，完成了从原点坐标系到真实坐标系的平移。

构造函数的随机种子

构造函数中显式调用rand.Seed(time.Now().UnixNano())以纳秒时间戳初始化全局随机数种子，避免每次程序启动都产生相同序列：

func Constructor(radius float64, x_center float64, y_center float64) Solution { rand.Seed(time.Now().UnixNano()) return Solution{radius, x_center, y_center} }

Solution结构体只保存三份状态：半径r、圆心横坐标x、圆心纵坐标y，与题目要求完全对应。

解题思路二：极坐标均匀采样（代码注释中保留）

在题解的RandPoint函数顶部，保留了一段被注释掉的极坐标实现：

/* a := angle() r := this.r * math.Sqrt(rand.Float64()) x := r * math.Cos(a) + this.x y := r * math.Sin(a) + this.y return []float64{x, y}*/

其配套的辅助函数angle()返回一个0, 2π)区间的随机角度：

func angle() float64 { return rand.Float64() * 2 * math.Pi }

这段被注释的代码之所以数学上更优雅，在于两个关键点：

1. 角度均匀采样：angle()用rand.Float64() * 2 * math.Pi产生[0, 2π)的随机角度，保证方向无偏；
2. 半径必须开方：r = this.r * math.Sqrt(rand.Float64())。这里rand.Float64()在[0,1)上均匀，直接取r = R * u会导致点集中在圆心附近（面积小的同心圆环被过度采样）。面积与r²成正比，因此需要对均匀量开方——r = R·√u才能让每个面积微元被命中的概率相等。这是「圆内均匀采样」最容易出错的数学细节。

极坐标法的优势是零拒绝、单次即可返回，时间复杂度严格为 O(1)；劣势是需要调用math.Sqrt、math.Cos、math.Sin三个超越函数。拒绝采样法只用到乘法与比较，无三角函数开销，且代码更直观。两种方法在本仓库中都以源码形式保留，方便读者对比学习。题解最终选择了拒绝采样作为正式提交版本，可推断是出于常数开销与代码可读性的综合考量。

单元测试与覆盖率验证

本仓库为每题都配套了单元测试，本题测试见 [478. Generate Random Point in a Circle_test.go：

func Test_Problem478(t *testing.T) { obj := Constructor(1, 0, 0) fmt.Printf("RandPoint() = %v\n", obj.RandPoint()) fmt.Printf("RandPoint() = %v\n", obj.RandPoint()) fmt.Printf("RandPoint() = %v\n", obj.RandPoint()) obj = Constructor(10, 5, -7.5) fmt.Printf("RandPoint() = %v\n", obj.RandPoint()) fmt.Printf("RandPoint() = %v\n", obj.RandPoint()) fmt.Printf("RandPoint() = %v\n", obj.RandPoint()) a := angle() if a < 0 || a >= 2*math.Pi { t.Fatalf("angle() = %v, want in [0, 2*Pi)", a) } fmt.Printf("angle() = %v\n", a) }

测试覆盖了两个关键场景：

• 两组典型构造参数：Constructor(1, 0, 0)（单位圆、原点）与Constructor(10, 5, -7.5)（对应题目示例二），各调用三次RandPoint()验证程序可正常运行并输出合理浮点坐标；
• angle()的区间合法性：显式断言返回角度满足0 ≤ a < 2π，从边界上验证了极坐标辅助函数的正确性。

此外，仓库根目录的 coverage.txt 记录了全库覆盖率数据，其中本题实现被完整执行：构造函数调用 2 次、RandPoint的拒绝循环与命中分支、angle()均被覆盖（对应记录位于github.com/halfrost/LeetCode-Go/leetcode/0478.Generate-Random-Point-in-a-Circle/...），符合仓库 "100% test coverage" 的整体要求。覆盖率统计由根目录的 gotest.sh 生成，其核心命令为：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

若要在本地复现测试结果，可在仓库根目录执行：

go test ./leetcode/0478.Generate-Random-Point-in-a-Circle/... -v

本仓库 go.mod 声明go 1.19，上述命令需在 Go 1.19 及以上环境中运行。

正确性与复杂度分析

• 正确性：拒绝采样保证返回点必然满足x² + y² ≤ R²（含圆周，符合题意）；候选点在正方形内均匀分布，条件概率下圆内点依然均匀；
• 时间复杂度：每次采样 O(1)，期望调用次数为1/(π/4) ≈ 1.27，总体期望 O(1)；
• 空间复杂度：O(1)，仅常数级状态。

延伸：如何验证采样均匀性

LeetCode 判题只校验「点在圆内」，不校验分布。若要在工程中验证均匀性，可统计大量采样点落入不同同心圆环（面积相等的环带）的频次，或计算各象限、各扇区的样本占比是否接近理论值。对拒绝采样实现，可额外记录拒绝率是否收敛到1 - π/4 ≈ 21.5%，以此侧面验证随机数生成与判定逻辑的正确性。

小结

本题是「几何区域均匀采样」的入门经典，LeetCode-Go 仓库的题解（README 题解文档、核心实现、单元测试）同时提供了拒绝采样与极坐标开方两种思路：前者以约 78.5% 的接受率换取简洁与低常数开销，后者以√u半径变换实现单次无拒绝采样。理解「均匀半径必须开方」与「拒绝采样收敛性」这两个核心点，即可举一反三，将同类技巧迁移到球面、多边形、不规则几何体等更复杂的均匀采样场景。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go