Medium

题目描述

给定圆的半径和圆心位置，实现函数 randPoint，该函数在圆内生成均匀分布的随机点。

实现 Solution 类：

  • 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 <= 10^8
  • -10^7 <= x_center, y_center <= 10^7
  • 最多调用 randPoint 3 * 10^4 次

解题思路

这道题要求在圆内均匀生成随机点，关键是理解"均匀分布"的含义。

有两种主要方法：

方法一：拒绝采样（Rejection Sampling） 最直观的想法是在包含圆的正方形内随机生成点，然后检查该点是否在圆内。如果在圆内就返回，否则重新生成。这种方法简单但效率较低，平均需要 π/4 ≈ 0.785 的成功率。

方法二：极坐标转换（推荐） 更高效的方法是使用极坐标。关键洞察是：如果直接对半径 r 进行均匀采样，会导致靠近圆心的点密度过高，因为同心圆的周长与半径成正比。

正确的做法是：

  1. 角度 θ 在 [0, 2π) 内均匀采样
  2. 半径 r 需要特殊处理：对 r² 在 [0, radius²] 内均匀采样，然后开根号得到 r

这样可以保证点在圆内的均匀分布，因为圆环面积与半径的平方成正比。

数学原理：在半径为 r 的圆环内，面积正比于 r²，所以累积分布函数应该是 r²/radius²，对应的逆函数是 radius × √(随机数)。

最后将极坐标 (r, θ) 转换为直角坐标 (x, y)，并平移到指定圆心。

代码实现

class Solution {
private:
    double radius;
    double x_center;
    double y_center;
    
public:
    Solution(double radius, double x_center, double y_center) {
        this->radius = radius;
        this->x_center = x_center;
        this->y_center = y_center;
        srand(time(nullptr));
    }
    
    vector<double> randPoint() {
        double angle = 2 * M_PI * ((double)rand() / RAND_MAX);
        double r = radius * sqrt((double)rand() / RAND_MAX);
        
        double x = x_center + r * cos(angle);
        double y = y_center + r * sin(angle);
        
        return {x, y};
    }
};

import random
import math

class Solution:
    def __init__(self, radius: float, x_center: float, y_center: float):
        self.radius = radius
        self.x_center = x_center
        self.y_center = y_center

    def randPoint(self) -> List[float]:
        angle = 2 * math.pi * random.random()
        r = self.radius * math.sqrt(random.random())
        
        x = self.x_center + r * math.cos(angle)
        y = self.y_center + r * math.sin(angle)
        
        return [x, y]

public class Solution {
    private double radius;
    private double xCenter;
    private double yCenter;
    private Random random;

    public Solution(double radius, double x_center, double y_center) {
        this.radius = radius;
        this.xCenter = x_center;
        this.yCenter = y_center;
        this.random = new Random();
    }
    
    public double[] RandPoint() {
        double angle = 2 * Math.PI * random.NextDouble();
        double r = radius * Math.Sqrt(random.NextDouble());
        
        double x = xCenter + r * Math.Cos(angle);
        double y = yCenter + r * Math.Sin(angle);
        
        return new double[] {x, y};
    }
}

var Solution = function(radius, x_center, y_center) {
    this.radius = radius;
    this.xCenter = x_center;
    this.yCenter = y_center;
};

Solution.prototype.randPoint = function() {
    const angle = 2 * Math.PI * Math.random();
    const r = this.radius * Math.sqrt(Math.random());
    
    const x = this.xCenter + r * Math.cos(angle);
    const y = this.yCenter + r * Math.sin(angle);
    
    return [x, y];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型拒绝采样方法极坐标转换方法（推荐）
时间复杂度O(1) 平均，最坏情况无界O(1)
空间复杂度O(1)O(1)

说明：

  • 极坐标转换方法的时间复杂度严格为 O(1)，每次调用只需要固定的计算量
  • 拒绝采样方法虽然平均时间复杂度为 O(1)，但理论上可能需要无限次重试
  • 两种方法的空间复杂度都是 O(1)，只需要常数额外空间

相关题目