Sponsored
Sponsored
Rejection sampling is a technique used to generate samples from a distribution by generating samples from a proposal distribution and then rejecting some of the samples. In the context of this problem, you can generate random points in a square that circumscribes the circle and then only accept those points that lie inside the circle.
Time Complexity: O(1) on average. Space Complexity: O(1) as no extra space is used.
1import random
2import math
3
4class Solution:
5 def __init__(self, radius: float, x_center: float, y_center: float):
6 self.radius = radius
7 self.x_center = x_center
8 self.y_center = y_center
9
10 def randPoint(self) -> List[float]:
11 while True:
12 x = random.uniform(-self.radius, self.radius)
13 y = random.uniform(-self.radius, self.radius)
14 if x * x + y * y <= self.radius * self.radius:
15 return [self.x_center + x, self.y_center + y]This solution uses a square of side double the radius centered at the (x_center, y_center) to generate random points. If the point lies within the circle (determined by the condition x^2 + y^2 <= radius^2), it is returned, otherwise the process is repeated.
Instead of generating points in a square and rejecting those outside the circle, we can directly generate points within the circle using polar coordinates. By randomly selecting an angle and a distance from the center, and then converting these polar coordinates to Cartesian coordinates, we can efficiently generate a uniform random point within the circle.
Time Complexity: O(1). Space Complexity: O(1).
1class Solution {
2 constructor(radius,
Using JavaScript, this solution similarly generates a random angle and a uniform radial distance (by taking the square root of a random value) which ensures the point falls within the circle. The Cartesian coordinates are calculated from polar form.