LC 478. 在圆内随机生成点

题目描述

这是 LeetCode 上的 478. 在圆内随机生成点 ，难度为 中等。

给定圆的半径和圆心的位置，实现函数 randPoint，在圆中产生均匀随机点。

实现 Solution 类:

  • Solution(double radius, double x_center, double y_center) 用圆的半径 radius 和圆心的位置 $(x_center, y_center)$ 初始化对象
  • randPoint() 返回圆内的一个随机点，圆周上的一点被认为在圆内，答案作为数组返回 $[x, y]$

示例 1：

1
2
3
4
5
6
7
8
9
10
输入: 
["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 <= 10^8$
  • $-10^7 <= x_center, y_center <= 10^7$
  • randPoint 最多被调用 $3 \times 10^4$ 次

等概率随机采样

为了方便，我们称圆心为 $(x, y)$，半径为 $r$。

对给定圆内的点进行等概率随机采样，容易想到随机化两个信息：一个是距离圆心的距离 len（在范围 $[0, r]$ 中进行随机），另外一个是夹角 ang（在范围 $[0, 2\pi]$ 中随机，随便找个参考线即可，例如以往 $x$ 轴正方向的射线为参考）。

然后根据 len 和 ang 直接计算对应的点的坐标，这样 可以确保随机出来的点一定在圆内，但并非「等概率」。

在不考虑夹角的情况下，我们本质是在 $[0, r]$ 范围内随机，这在「一维」上「等概率」是成立的，因为满足「任意连续段中点被抽到的次数与总次数的比例」与「该连续段长度与总长度的比例」。

但在圆中并非如此，不考虑夹角时，「任意连续段 len 与总长度 r 的比例」和「len 对应面积与总面积比例」并不相等。例如 len 有 $\frac{1}{2}$ 的概率取到小于等于 $\frac{r}{2}$ 的值，而半径为 $\frac{r}{2}$ 扫过的面积仅为总面积的 $\frac{1}{4}$，因此我们的 len 不能直接在 $[0, r]$ 范围内随机，为了消除这种一维转圆导致的「等概率」失效，我们可以从 $[0, r^2]$ 内随机再开平方，从而确保距离与面积比例一致。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    double r, x, y;
    Random random = new Random();
    public Solution(double _r, double _x, double _y) {
        r = _r; x = _x; y = _y;
    }
    public double[] randPoint() {
        double len = Math.sqrt(random.nextDouble(r * r)), ang = random.nextDouble(2 * Math.PI);
        double nx = x + len * Math.cos(ang), ny = y + len * Math.sin(ang);
        return new double[]{nx, ny};
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    double r, x, y;
    Solution(double _r, double _x, double _y) {
        r = _r; x = _x; y = _y;
    }
    vector<double> randPoint() {
        double a = static_cast<double>(rand()) / RAND_MAX, b = static_cast<double>(rand()) / RAND_MAX;
        double len = sqrt(a * r * r);
        double ang = b * 2 * M_PI;
        double nx = x + len * cos(ang);
        double ny = y + len * sin(ang);
        return {nx, ny};
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def __init__(self, r: float, x: float, y: float):
        self.r = r
        self.x = x
        self.y = y

    def randPoint(self) -> List[float]:
        lenv = math.sqrt(random.random() * self.r * self.r)
        ang = random.random() * 2 * math.pi
        nx = self.x + lenv * math.cos(ang)
        ny = self.y + lenv * math.sin(ang)
        return [nx, ny]

TypeScript 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    private r: number;
    private x: number;
    private y: number;
    private random: () => number;
    constructor(r: number, x: number, y: number) {
        this.r = r;
        this.x = x;
        this.y = y;
        this.random = () => Math.random();
    }
    randPoint(): number[] {
        const len = Math.sqrt(this.random() * this.r * this.r);
        const ang = this.random() * 2 * Math.PI;
        const nx = this.x + len * Math.cos(ang);
        const ny = this.y + len * Math.sin(ang);
        return [nx, ny];
    }
}

  • 时间复杂度：$O(1)$
  • 空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.478 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。