LeetCode478. 在圆内随机生成点

题目描述

本题目来自LeetCode上的『LeetCode478.在圆内随机生成点』

给定圆的半径和圆心，实现一个函数，可以在圆中产生均匀随机点。

示例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]

题解

如果不考虑等概率，直接返回圆心就行（笑

考虑等概率的话，就需要一番分析啦，本文从两个角度进行讲解。

角度1 - 几何概型角度

首先考虑一个朴素的几何概型想法：

在 [0,r] 的线段上随机取值，取到 [0,r2] 的概率为 12，现在将这个线段的一端固定，另一端旋转一周，线段扫过的图形为一个以 r 为半径的圆，此时线段 [0,r2] 扫过的圆面积为整个圆面积的 14，圆内随机取一个点，这个点落在小圆的概率为 14。因此，在一维中等概率取一点，旋转成圆之后就不是等概率了。

角度2 - 概率论角度

下面从概率论角度分析。

不失一般性，我们以单位圆为例，在单位圆上任取一点，这个点落到某一圆周上的长度与该圆周的周长成正比，从而也就与该圆周的半径成正比，设单位圆的概率密度函数 f(r)=kr，因此：

1=P(0≤r≤1)=∫10kr dr=12k

得 k=2，PDF：f(r)=2r

得到PDF后，就可以算出分布函数CDF：

F(r)=∫r0f(t) dt=r2

通过上面的分析，想要得到等概率，需要在 [0,1] 内等概率取 F(r) 的值，r=√F(r)，然后再对单位圆进行放缩。

坐标生成

根据极坐标生成圆心的坐标：

{ρ2=x2+y2x=ρcosθy=ρsinθ

其中，θ 可在 [0,2π] 中等概率生成。

代码

cpp

class Solution {
private:
    const double PI = acos(-1);
    double r, x, y;
    mt19937 gen{ random_device{}() };
    uniform_real_distribution<double> dis;
public:
    Solution(double radius, double x_center, double y_center) :
    r(radius), x(x_center), y(y_center), dis(0, 1) { }
    
    vector<double> randPoint() {
        double theta = dis(gen) * 2 * PI;
        double rho = sqrt(dis(gen)) * r;
        return {x + rho * cos(theta), y + rho * sin(theta)};
    }
};

复杂度分析

不考虑生成随机数的复杂度

• 时间复杂度：O(1)

• 空间复杂度：O(1)