LeetCode 478. 在圆内随机生成点

核心思路

关键点在于「均匀」二字。很多人第一反应是：

// ❌ 错误做法doubler=radius*Math.random();doubletheta=2*Math.PI*Math.random();

这样会导致点集中在圆心附近。原因是面积元是 dA = r·dr·dθ，半径越大对应的面积越大，所以半径应按 √U 分布而不是线性。

证明：距圆心 R 内的面积占总体比例 F® = πR² / πr² = (R/r)²，由反函数采样 R = r·√U。

实现一：极坐标 + 开根号（推荐，O(1)）

classSolution{privatedoubleradius,xCenter,yCenter;privateRandomrandom=newRandom();publicSolution(doubleradius,doublex_center,doubley_center){this.radius=radius;this.xCenter=x_center;this.yCenter=y_center;}publicdouble[]randPoint(){// 半径按 sqrt 采样，保证面积均匀doubler=radius*Math.sqrt(random.nextDouble());doubletheta=2*Math.PI*random.nextDouble();returnnewdouble[]{xCenter+r*Math.cos(theta),yCenter+r*Math.sin(theta)};}}

实现二：拒绝采样（同样正确，期望 O(1)）

在外接正方形内取点，不在圆内就重试。命中率 = π/4 ≈ 78.5%，期望约 1.27 次即可。

classSolution{privatedoubleradius,xCenter,yCenter;privateRandomrandom=newRandom();publicSolution(doubleradius,doublex_center,doubley_center){this.radius=radius;this.xCenter=x_center;this.yCenter=y_center;}publicdouble[]randPoint(){while(true){doubledx=(2*random.nextDouble()-1)*radius;doubledy=(2*random.nextDouble()-1)*radius;if(dx*dx+dy*dy<=radius*radius){returnnewdouble[]{xCenter+dx,yCenter+dy};}}}}

复杂度对比

方法 时间 空间 备注
极坐标 + sqrt O(1) 确定 O(1) 无循环，最稳
拒绝采样 O(1) 期望 O(1) 实现直观，最坏情况无上界

常见坑

1. 不要漏掉 Math.sqrt —— 否则点会向圆心聚集。
2. 角度范围用 2π（弧度），不要用 360。
3. Random.nextDouble() 返回 [0,1)，注意乘的系数。
4. 精确比较 <= radius * radius，避免开方带来的浮点误差。

面试中建议答极坐标法，并说明 sqrt 的数学原因，这是这题最大的加分点。