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
| class Solution {
private final int[][] rects;
public Solution(int[][] rects) {
this.rects = rects;
}
public int[] pick() {
int selectIndex = -1;
int totalPoints = 0;
for (int i = 0; i < rects.length; i++) {
int[] rect = rects[i];
int points = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
totalPoints += points;
if (ThreadLocalRandom.current().nextInt(totalPoints) < points) {
selectIndex = i;
}
}
int[] rect = rects[selectIndex];
int randomX = rect[0] + ThreadLocalRandom.current().nextInt(rect[2] - rect[0] + 1);
int randomY = rect[1] + ThreadLocalRandom.current().nextInt(rect[3] - rect[1] + 1);
return new int[]{randomX, randomY};
}
}
|
References
497. Random Point in Non-overlapping Rectangles
【蓄水池抽样】多语言入门「蓄水池抽样」知识点