题目

给定一个由非重叠的轴对齐矩形的数组 rects ，其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点，(xi, yi) 是第 i 个矩形的右上角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被矩形覆盖。所有满足要求的点必须等概率被返回。

在给定的矩形覆盖的空间内的任何整数点都有可能被返回。

请注意 ，整数点是具有整数坐标的点。

实现 Solution 类:

Solution(int[][] rects) 用给定的矩形数组 rects 初始化对象。
int[] pick() 返回一个随机的整数点 [u, v] 在给定的矩形所覆盖的空间内。

示例 1： 497. 非重叠矩形中的随机点 - 图1 输入:
[“Solution”, “pick”, “pick”, “pick”, “pick”, “pick”]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
输出:
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]

解释：
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // 返回 [1, -2]
solution.pick(); // 返回 [1, -1]
solution.pick(); // 返回 [-1, -2]
solution.pick(); // 返回 [-2, -2]
solution.pick(); // 返回 [0, 0]

提示：

1 <= rects.length <= 100
rects[i].length == 4
-10^9 <= ai < xi <= 10^9
-10^9 <= bi < yi <= 10^9
xi - ai <= 2000
yi - bi <= 2000
所有的矩形不重叠。
pick 最多被调用 10^4 次。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/random-point-in-non-overlapping-rectangles
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

一个矩形被选中的概率与其之内点的个数成正比。

计算每个矩形中点的数目，存储在一个数组中，计算该数组的前缀和数组，随机生成一个[0,sum)中的数，落在哪两个数之间，对应的该矩形就是被随机选中的矩形。实现时，可以使用有序集合存储前缀和，这里使用TreeMap，key为到当前矩形的前缀和，value为该矩形在原始数组的下标。

随机数确定的同时，其实点的位置也随之确定。

代码

  1. class Solution {
  2.     TreeMap<Integer, Integer> map;
  3.     int sum = 0;
  4.     int[][] rects;
  6.     public Solution(int[][] rects) {
  7.         this.rects = rects;
  8.         map = new TreeMap<>();
  9.         int n = rects.length;
  10.         for (int i = 0; i < n; i++) {
  11.             map.put(sum, i);
  12.             sum += (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
  13.         }
  14.     }
  16.     public int[] pick() {
  17.         int num = (int) (Math.random() * sum);
  18.         Integer floor = map.floorKey(num);
  19.         int index = map.get(floor);
  20.         // 矩形的高
  21.         int col = rects[index][3] - rects[index][1] + 1;
  22.         // x方向相对于左下角顶点的偏移量
  23.         int x = (area - floor) / col;
  24.         // y方向相对于左下角顶点的偏移量
  25.         int y = (area - floor) % col;
  26.         return new int[]{rects[index][0] + x, rects[index][1] + y};
  27.     }
  28. }
  29. /**
  30.  * Your Solution object will be instantiated and called as such:
  31.  * Solution obj = new Solution(rects);
  32.  * int[] param_1 = obj.pick();
  33.  */