DeepSeek LeetCode 478. 在圆内随机生成点 Java实现

LeetCode 478. 在圆内随机生成点核心思路关键点在于「均匀」二字。很多人第一反应是// ❌ 错误做法doublerradius*Math.random();doubletheta2*Math.PI*Math.random();这样会导致点集中在圆心附近。原因是面积元是 dA r·dr·dθ半径越大对应的面积越大所以半径应按 √U 分布而不是线性。证明距圆心 R 内的面积占总体比例 F® πR² / πr² (R/r)²由反函数采样 R r·√U。实现一极坐标 开根号推荐O(1)classSolution{privatedoubleradius,xCenter,yCenter;privateRandomrandomnewRandom();publicSolution(doubleradius,doublex_center,doubley_center){this.radiusradius;this.xCenterx_center;this.yCentery_center;}publicdouble[]randPoint(){// 半径按 sqrt 采样保证面积均匀doublerradius*Math.sqrt(random.nextDouble());doubletheta2*Math.PI*random.nextDouble();returnnewdouble[]{xCenterr*Math.cos(theta),yCenterr*Math.sin(theta)};}}实现二拒绝采样同样正确期望 O(1)在外接正方形内取点不在圆内就重试。命中率 π/4 ≈ 78.5%期望约 1.27 次即可。classSolution{privatedoubleradius,xCenter,yCenter;privateRandomrandomnewRandom();publicSolution(doubleradius,doublex_center,doubley_center){this.radiusradius;this.xCenterx_center;this.yCentery_center;}publicdouble[]randPoint(){while(true){doubledx(2*random.nextDouble()-1)*radius;doubledy(2*random.nextDouble()-1)*radius;if(dx*dxdy*dyradius*radius){returnnewdouble[]{xCenterdx,yCenterdy};}}}}复杂度对比方法 时间 空间 备注极坐标 sqrt O(1) 确定 O(1) 无循环最稳拒绝采样 O(1) 期望 O(1) 实现直观最坏情况无上界常见坑不要漏掉 Math.sqrt —— 否则点会向圆心聚集。角度范围用 2π弧度不要用 360。Random.nextDouble() 返回 [0,1)注意乘的系数。精确比较 radius * radius避免开方带来的浮点误差。面试中建议答极坐标法并说明 sqrt 的数学原因这是这题最大的加分点。