LeetCode-Go 题解 478Generate 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该函数在圆中生成一个均匀随机点。原题给出了四条关键说明输入和输出值都是浮点数圆的半径和圆心的 x、y 坐标通过类构造函数传入圆周上的点也认为在圆中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是半径。题目要求「均匀随机」意味着圆内每一小块面积被命中的概率应当与它的面积成正比——这是本题最容易踩坑的地方下文会重点对比两种算法在均匀性上的差异。解题思路一拒绝采样本题解采用仓库题解见 核心实现源码采用的思路如下先假设圆心在 (0,0)这样便于计算最终输出坐标时整体加上圆心偏移量即可用rand.Float64()产生[0.0, 1.0)区间的浮点数构造-R ≤ 2 * R * rand() - R R的横纵坐标候选点判断候选点是否满足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*xy*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*xy*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 }这段被注释的代码之所以数学上更优雅在于两个关键点角度均匀采样angle()用rand.Float64() * 2 * math.Pi产生[0, 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.gofunc 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 -covermodeatomic -coverprofilecoverage.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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Go 题解 478Generate 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该函数在圆中生成一个均匀随机点。原题给出了四条关键说明输入和输出值都是浮点数圆的半径和圆心的 x、y 坐标通过类构造函数传入圆周上的点也认为在圆中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是半径。题目要求「均匀随机」意味着圆内每一小块面积被命中的概率应当与它的面积成正比——这是本题最容易踩坑的地方下文会重点对比两种算法在均匀性上的差异。解题思路一拒绝采样本题解采用仓库题解见 核心实现源码采用的思路如下先假设圆心在 (0,0)这样便于计算最终输出坐标时整体加上圆心偏移量即可用rand.Float64()产生[0.0, 1.0)区间的浮点数构造-R ≤ 2 * R * rand() - R R的横纵坐标候选点判断候选点是否满足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*xy*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*xy*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 }这段被注释的代码之所以数学上更优雅在于两个关键点角度均匀采样angle()用rand.Float64() * 2 * math.Pi产生[0, 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.gofunc 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 -covermodeatomic -coverprofilecoverage.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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
