教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文基于「算法通关手册」AlgoNote 仓库中的 LeetCode 0478 题解展开系统讲解如何实现randPoint()在给定圆内生成均匀随机点。文章以**拒绝采样Rejection Sampling**为核心从题目约束、采样原理、代码实现到复杂度分析层层递进并给出「为什么不能直接对半径和角度均匀采样」的数学解释。读完本文你将掌握拒绝采样的一般套路并能将其迁移到 Rand7 生成 Rand10、非重叠矩形随机取点等同类随机化问题。题目概述与接口设计LeetCode 0478「在圆内随机生成点」要求设计一个Solution类在给定圆内产生均匀随机点Solution(double radius, double x_center, double y_center)用圆的半径radius和圆心位置(x_center, y_center)初始化对象randPoint()返回圆内的一个随机点圆周上的点同样视为在圆内结果以[x, y]数组返回。题目的关键数据约束原文档已明确给出半径0 radius 10^8圆心坐标-10^7 x_center, y_center 10^7调用次数randPoint()最多被调用3 * 10^4次。示例调用如下原文档示例输入: [Solution,randPoint,randPoint,randPoint] [[1.0, 0.0, 0.0], [], [], []] 输出: [null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]本题标签为「几何、数学、拒绝采样、随机化」难度中等属于典型的随机化 计算几何组合题。在 AlgoNote 仓库的题解目录 docs/solutions/0400-0499/index.md 中它与 0497. 非重叠矩形中的随机点 同属随机化专题适合对照阅读。思路 1拒绝采样Rejection Sampling核心原理要在圆内生成均匀随机点最直观、实现最简单的方法是拒绝采样先在圆的外接正方形区域里均匀撒点再把落在圆外的点丢掉只保留圆内的点。具体算法步骤如下继承自原文档在圆的外接正方形区域内随机生成点[x, y]其中x ∈ [x_center - radius, x_center radius]y ∈ [y_center - radius, y_center radius]判断点是否在圆内计算点与圆心的距离dist sqrt((x - x_center)^2 (y - y_center)^2)若dist radius接受该点否则拒绝重新生成重复生成直到得到一个在圆内的点。这里「均匀」的关键在于正方形区域内的随机点服从均匀分布而圆是正方形的一个子集因此被接受的那些点在整个圆内同样均匀分布——拒绝操作只是等概率地过滤掉圆外区域不会破坏接受点内部的均匀性。为什么不能直接对半径和角度均匀采样拒绝采样之外另一个常见想法是使用极坐标令半径r在[0, radius]均匀取值、角度θ在[0, 2π]均匀取值再转换回直角坐标。这种做法是错误的单位面积上的点密度取决于到圆心的距离靠近圆心的区域面积小、靠近圆周的区域面积大若r均匀分布点的分布会向圆心聚集无法满足「圆内均匀随机点」的要求。正确做法需要对半径的平方均匀采样即令r radius * sqrt(u)u均匀分布这正是拒绝采样绕开该问题的价值所在——它完全不依赖极坐标变换实现直观且不易出错。完整代码实现原文档给出的 Python 实现如下import random class Solution: def __init__(self, radius: float, x_center: float, y_center: float): self.radius radius # 圆的半径 self.x_center x_center # 圆心 x 坐标 self.y_center y_center # 圆心 y 坐标 def randPoint(self) - List[float]: # 在外接正方形内生成随机点 while True: # 生成 [x_center - radius, x_center radius] 范围内的随机 x 坐标 x random.uniform(self.x_center - self.radius, self.x_center self.radius) # 生成 [y_center - radius, y_center radius] 范围内的随机 y 坐标 y random.uniform(self.y_center - self.radius, self.y_center self.radius) # 计算点到圆心的距离 dist ((x - self.x_center) ** 2 (y - self.y_center) ** 2) ** 0.5 # 如果点在圆内包括圆周上则接受该点 if dist self.radius: return [x, y] # Your Solution object will be instantiated and called as such: # obj Solution(radius, x_center, y_center) # param_1 obj.randPoint()实现细节说明random.uniform(a, b)返回[a, b]区间内的均匀浮点数边界radius极大可达10^8也不会溢出因为 Python 浮点数采用双精度表示判断条件使用dist self.radius而非严格小于与题意「圆周上的一点被认为在圆内」保持一致由于randPoint()最坏可能循环多次代码中while True循环配合条件返回是拒绝采样的标准写法。复杂度分析原文档给出的复杂度结论为时间复杂度O(1)期望时间复杂度。正方形面积为(2r)^2 4r^2圆面积为πr^2单次采样落在圆内的成功率即接受率为p πr^2 / (2r)^2 π/4 ≈ 0.785因此期望生成次数为1/p ≈ 1.27即平均不到 2 次采样即可成功为常数级。空间复杂度O(1)。只使用了radius、x_center、y_center等常数个变量。需要说明的是这里的O(1)是期望意义下的复杂度拒绝采样以概率p接受单次采样失败后重试几何分布下的期望重试次数为1/p与输入规模无关因此整体仍视为常数期望。仓库的复杂度理论章节 docs/00_preface/00_03_algorithm_complexity.md 中也指出「平均时间复杂度」即随机输入下的期望时间复杂度可供对照理解。拒绝采样一类随机化问题的通用范式拒绝采样并非只适用于本题。在 AlgoNote 仓库的题解中拒绝采样思想还出现在0470. 用 Rand7() 实现 Rand10()调用两次rand7()映射出[1, 49]均匀整数只接受[1, 40]的部分拒绝[41, 49]从而保证[1, 10]每个数字出现次数完全相等。其接受率为40/49期望调用rand7()约2.45次0497. 非重叠矩形中的随机点按矩形面积加权随机选中一个矩形后再在其中取点本质上是把「按面积比例均匀撒点」的拒绝思想用加权随机 二分查找显式实现。三者的共同模式可归纳为在一个容易均匀采样的候选区域正方形、大整数区间、加权矩形中生成候选点设计一个几何/数值判定条件dist radius、num 40、二分定位矩形索引区分可接受与需拒绝的样本只返回满足条件的样本从而在目标区域上保持均匀分布。这个范式的代价是「部分样本被浪费」但换来的是实现简单、均匀性有严格数学保证且当接受率接近 1 时开销极低。本题接受率约 78.5%属于非常划算的用法即使接受率较低如高维情形拒绝采样依然是蒙特卡洛方法中不可或缺的基础工具。小结LeetCode 0478 的核心考点有三一是理解「圆内均匀」的数学含义二是掌握拒绝采样的标准流程三是能分析其期望时间复杂度。AlgoNote 仓库将本题收录于 docs/solutions/0400-0499/index.md完整题解列表可在 docs/00_preface/00_05_solutions_list.md 中检索。建议在掌握本题后进一步完成 0470. 用 Rand7() 实现 Rand10() 与 0497. 非重叠矩形中的随机点 两题即可系统掌握随机化与拒绝采样这一完整题型的解法脉络。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐GeoPandas数据采样技术均匀分布和随机点生成算法GeoPandas数据采样技术均匀分布和随机点生成算法 GeoPandas作为Python地理数据处理的核心工具提供了强大的空间数据采样能力。通过内置的均匀数据分析GISLeetCode-Go 题解 478Generate Random Point in a Circle 圆内均匀随机取点LeetCode Go 题解 478Generate Random Point in a Circle 圆内均匀随机取点 导读 本文基于 LeetCode G示例工程Open3D均匀采样技术从新手到专家的3D数据处理完整指南Open3D均匀采样技术从新手到专家的3D数据处理完整指南 Open3D作为现代3D数据处理的强大库其均匀采样技术是处理点云和网格数据的核心功能之一。 Op计算机视觉图形学3D渲染科学计算上一篇终极指南如何用Pearcleaner彻底解决macOS应用残留文件问题下一篇Flutter video_player 平台接口演进全解析从 VideoPlayerPlatform 到音视频轨道与播放能力扩展创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考