497. 非重叠矩形中的随机点

难度 medium
给定一个非重叠轴对齐矩形的列表 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：

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

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

输入语法的说明：

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

解题思路：这是一个相对来说没有固定输出的题目，随机点落在哪个矩形中的概率和矩形大小成正比，因此我们需要在计算矩形面积的大小，对应一个概率值，然后用一个rand函数来生成一个随机数，看看落在哪个区间，然后选择相应的矩形，在这个矩形内再随机选点。看了网上的一个题解，用area_sum记录所有矩形的面积总和，当然这个值在我们计算矩形面积的过程中会不断更新，然后每当我们计算一个矩形面积，我们先将area加到area_sum中，然后用rand()%area_sum和area作比较，如果小于这个area，我们就默认这个area是我们最后选定的矩形。为什么这样计算？其实这种方法和上面提到的每个矩形对应一个概率区间，然后再用随机数来选区间的方法是一样的，rand()%area_sum就是一个位于[0,area_sum]之间的数，我们把area_sum想象成一条线型区间，当前计算的矩形面积是area，相当于占据了前面area的区间长度，如果rand()%area_sum处于这个区间内，我们就选择当前这个矩形，这其实就是在计算它的概率值。rand()的每个输出之间相互没有影响，因此我们无论调用一次还是多次，最终选择哪个区间都是根据他们的面积大小也就是概率值来决定的，因此可以用上面那种方法。

代码 t37 s84 java

class Solution {

    public Solution(int[][] rects) {
        _rects = rects;
    }
    
    public int[] pick() {
        int area_sum = 0;
        Random rand = new Random();
        int[] selected = new int[4];
        for(int[] rect : _rects){
            int area = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
            area_sum += area;
            if(rand.nextInt(Integer.MAX_VALUE) % area_sum < area) selected = rect;
        }
        int x = rand.nextInt(Integer.MAX_VALUE) % (selected[2] - selected[0] + 1) + selected[0];
        int y = rand.nextInt(Integer.MAX_VALUE) % (selected[3] - selected[1] + 1) + selected[1];
        return new int[]{x, y};
    }

    private int[][] _rects;
}

参考资料：
https://www.cnblogs.com/grandyang/p/9752145.html

497. 非重叠矩形中的随机点

原文：https://www.cnblogs.com/zhengxch/p/14727075.html