Medium

497. Random Point in Non-overlapping Rectangles

arraymathbinary-searchreservoir-samplingprefix-sumordered-setrandomized

解題說明

Random Point in Non-overlapping Rectangles

題目描述：給定多個不重疊的軸對齊矩形，實作 pick() 方法，在所有矩形覆蓋的整數點中均勻隨機選取一個點。

解題思路：每個矩形 [a, b, c, d] 包含 (c-a+1)*(d-b+1) 個整數點。首先計算每個矩形的點數並建立前綴和陣列。選點時，先隨機生成一個 [0, totalPoints-1] 的數字，用二元搜尋找到該數字落在哪個矩形的前綴和區間內。然後在該矩形內將剩餘的偏移量轉換為具體的 (x, y) 座標。

C++ 解法

複雜度分析

時間複雜度：建構 O(n)，pick O(log n) — 其中 n 為矩形數量，二元搜尋找到目標矩形。

空間複雜度：O(n) — 前綴和陣列。

虛擬碼

1. Constructor:
   a. For each rectangle, compute number of integer points = (c-a+1)*(d-b+1)
   b. Build prefix sum array of cumulative point counts
2. Pick():
   a. Generate random number target in [0, totalPoints - 1]
   b. Binary search in prefix sum to find which rectangle target falls into (index idx)
   c. Compute offset = target - prefixSum[idx-1] (or target if idx == 0)
   d. width = rects[idx][2] - rects[idx][0] + 1
   e. x = rects[idx][0] + offset % width
   f. y = rects[idx][1] + offset / width
   g. Return [x, y]

其他解法

蓄水池抽樣 O(n) per pick：不預處理前綴和，每次 pick 時遍歷所有矩形使用蓄水池抽樣選取一個矩形，再在其中隨機選點。不需要額外空間但每次 pick 為 O(n) 而非 O(log n)。

展平所有點 O(total)：將所有矩形的整數點列舉出來存入陣列，每次直接隨機取索引。pick 為 O(1) 但預處理和空間都是 O(total)，當矩形很大時不可行。

延伸思考

如果矩形是浮點座標且要在連續區域內均勻取點（而非整數點），該如何修改？
如果矩形可以重疊，如何確保均勻性？
能否支援動態新增和刪除矩形？

Random Point in Non-overlapping Rectangles — CaffeCode