LeetCode-478. 在圆内随机生成点【几何 数学 拒绝采样 随机化】
题目描述：
给定圆的半径和圆心的位置，实现函数 randPoint ，在圆中产生均匀随机点。
Solution(double radius, double x_center, double y_center) 用圆的半径 radius 和圆心的位置 (x_center, y_center) 初始化对象
randPoint() 返回圆内的一个随机点。圆周上的一点被认为在圆内。答案作为数组返回 [x, y] 。
示例 1：
输入:
[“Solution”,“randPoint”,“randPoint”,“randPoint”]
[[1.0, 0.0, 0.0], [], [], []]
输出: [null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]
解释:
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint ();//返回[-0.02493，-0.38077]
solution.randPoint ();//返回[0.82314,0.38945]
solution.randPoint ();//返回[0.36572,0.17248]
提示：
0 < radius <= 108
-107 <= x_center, y_center <= 107
randPoint 最多被调用 3 * 104 次
解题思路一：一个最简单的方法就是在一个正方形内生成随机采样的点，然后拒绝不在内切圆中的采样点。
class Solution:
def __init__(self, radius: float, x_center: float, y_center: float):
self.r = radius
self.x = x_center
self.y = y_center
def randPoint(self) -> List[float]:
while True:
x, y =random.uniform(-self.r, self.r), random.uniform(-self.r, self.r)
if x*x +y*y <= self.r * self.r:
return [self.x + x, self.y + y]
# Your Solution object will be instantiated and called as such:
# obj = Solution(radius, x_center, y_center)
# param_1 = obj.randPoint()
调用的期望次数是圆的面积除以正方形的面积。即(2R)2/πR2约等于0.785即O(1)，也就是时间复杂度。
时间复杂度：O(1)
空间复杂度：O(1)
解题思路二：具体思想是先生成一个0到r的随机数len，然后生成一个随机的角度来生成对应的坐标。但是这样并不是等概率的，因为例如 len 有
1
2
frac{1}{2}
21的概率取到小于等于
r
2
frac{r}{2}
2r的值，而半径为
r
2
frac{r}{2}
2r扫过的面积仅为总面积的
1
4
frac{1}{4}
41，因此我们的 len 不能直接在[0, r]范围内随机，为了消除这种一维转圆导致的「等概率」失效，我们可以从[0, r2]内随机再开平方，从而确保距离与面积比例一致。
class Solution:
def __init__(self, radius: float, x_center: float, y_center: float):
self.r = radius
self.x = x_center
self.y = y_center
def randPoint(self) -> List[float]:
u, theta = random.random(), random.random()*2*math.pi
r = sqrt(u)
return [self.x + r*math.cos(theta)*self.r, self.y + + r*math.sin(theta)*self.r]
解题思路三：0
原文地址:https://blog.csdn.net/qq_45934285/article/details/134808187
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_49396.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
