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

Difficulty
Medium
Tags
二分查找
URL
https://leetcode.cn/problems/random-point-in-non-overlapping-rectangles/
Star
给定一个由非重叠的轴对齐矩形的数组 rects ，其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点，(xi, yi) 是第 i 个矩形的右上角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被矩形覆盖。所有满足要求的点必须等概率被返回。
在给定的矩形覆盖的空间内的任何整数点都有可能被返回。
请注意 ，整数点是具有整数坐标的点。
实现 Solution 类:
  • Solution(int[][] rects) 用给定的矩形数组 rects 初始化对象。
  • int[] pick() 返回一个随机的整数点 [u, v] 在给定的矩形所覆盖的空间内。
示例 1：
notion imagenotion image
输入:
["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
  • 109 <= ai < xi <= 109
  • 109 <= bi < yi <= 109
  • xi - ai <= 2000
  • yi - bi <= 2000
  • 所有的矩形不重叠。
  • pick 最多被调用 104 次。
通过次数10,708提交次数25,786

法1 二分查找

思路
参考
🏨
528. 按权重随机选择.
本题的思路为：
  1. 先选择某个矩形
  1. 然后再在该矩形上 随机选取某点，[random.randint(x_s, x_e), random.randint(y_s, y_e)]
所以关键在于如何随机选择某个矩形。随机选择该矩形的权重应该和矩形中的点的数据成正比，有点类似
🏨
528. 按权重随机选择 中按权重随机选择。
我们的做法也和该题类似，将矩形的面积转化为数组值，然后用528的方式随机选择某个矩形
题解