给定一个非重叠轴对齐矩形的列表 rects，写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。

提示：

  • 整数点是具有整数坐标的点。
  • 矩形周边上的点包含在矩形覆盖的空间中。
  • 第 i 个矩形 rects [i] = [x1，y1，x2，y2]，其中 [x1，y1] 是左下角的整数坐标，[x2，y2] 是右上角的整数坐标。
  • 每个矩形的长度和宽度不超过 2000。
  • 1 <= rects.length <= 100
  • pick 以整数坐标数组 [p_x, p_y] 的形式返回一个点。

  • pick 最多被调用10000次。


    示例 1：

    1. 输入: 
    2. ["Solution","pick","pick","pick"]
    3. [[[[1,1,5,5]]],[],[],[]]
    4. 输出: 
    5. [null,[4,1],[4,1],[3,3]]

    示例 2：

    1. 输入: 
    2. ["Solution","pick","pick","pick","pick","pick"]
    3. [[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
    4. 输出: 
    5. [null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]

    输入语法的说明：
    输入是两个列表：调用的子例程及其参数。Solution 的构造函数有一个参数，即矩形数组 rects。pick 没有参数。参数总是用列表包装的，即使没有也是如此。

题解

看题目一脸懵逼！后天面试可咋办呢😿

用 w[i]表示第 i 个矩形 rect[i] 中整数点的数目，那么随机算法需要使得每个矩形被选到的概率与 w[i] 成正比（这样也就保证了空间中的每个整数点被选到的概率都是相等的）。具体地，rect[i]被选到的概率应当为 w[i] / sum(w[i])，其中 sum(w[i]) 表示空间中的整数点数目之和。

令 tot = sum(w[i])，就可以在 [0, tot) 区间内生成随机整数。假设生成的数为 x，那么我们需要找到满足 prefix(w[i - 1]) <= x < prefix(w[i]) 的 i，其中 prefix(w[i]) 表示前i个矩形中整数点的数目之和，此时选中了第 i 个矩形。就可以使用二分查找，找出对应的 i。

在选中了第i个矩形后，也可以在 [0, w[i]) 中再次生成随机数，来在这个矩形中随机选择一个点。更好的做法是仍然使用之前生成的数 x，令 y = x - prefix(w[i - 1])，只需要选择第 i 个矩形中的第 y 个点即可，对应的坐标为：

x_coord = x_start + y % (x_end - x_start + 1)
y_coord = y_start + y / (x_end - x_start + 1)

这相当于把第 i 个矩形中的坐标按照 y 轴优先的顺序依次排列，每一个点都可以通过上述的方式恢复到矩形中的坐标。