497. Random Point in Non-overlapping Rectangles¶

• Time: Constructor: $O(n)$, pick(): $O(\log n)$;
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public: Solution(vector>& rects) : rects(move(rects)) { for (const vector& r : this->rects) areas.push_back(getArea(r)); partial_sum(areas.begin(), areas.end(), areas.begin()); } vector pick() { const int target = rand() % areas.back(); const int index = ranges::upper_bound(areas, target) - areas.begin(); const vector& r = rects[index]; return {rand() % (r[2] - r[0] + 1) + r[0], rand() % (r[3] - r[1] + 1) + r[1]}; } private: const vector> rects; vector areas; int getArea(const vector& r) { return (r[2] - r[0] + 1) * (r[3] - r[1] + 1); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public Solution(int[][] rects) { this.rects = rects; areas = new int[rects.length]; for (int i = 0; i < rects.length; ++i) areas[i] = getArea(rects[i]) + (i > 0 ? areas[i - 1] : 0); } public int[] pick() { final int target = rand.nextInt(areas[areas.length - 1]); final int index = firstGreater(areas, target); final int[] r = rects[index]; return new int[] { rand.nextInt(r[2] - r[0] + 1) + r[0], rand.nextInt(r[3] - r[1] + 1) + r[1], }; } private int[][] rects; private int[] areas; private Random rand = new Random(); private int getArea(int[] r) { return (r[2] - r[0] + 1) * (r[3] - r[1] + 1); } private int firstGreater(int[] A, int target) { final int i = Arrays.binarySearch(A, target + 1); return i < 0 ? -i - 1 : i; } } 
  1 2 3 4 5 6 7 8 9 10 class Solution: def __init__(self, rects: List[List[int]]): self.rects = rects self.areas = list(itertools.accumulate( [(x2 - x1 + 1) * (y2 - y1 + 1) for x1, y1, x2, y2 in rects])) def pick(self) -> List[int]: index = bisect_right(self.areas, random.randint(0, self.areas[-1] - 1)) x1, y1, x2, y2 = self.rects[index] return [random.randint(x1, x2), random.randint(y1, y2)]