问题描述 链接到标题

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

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

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

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

实现 Solution 类:

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

示例 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⁹ <= aᵢ < xᵢ <= 10⁹
  • -10⁹ <= bᵢ < yᵢ <= 10⁹
  • xᵢ - aᵢ <= 2000
  • yᵢ - bᵢ <= 2000
  • 所有的矩形不重叠。
  • pick 最多被调用 10⁴ 次。

解题思路 链接到标题

前缀和+二分 前缀和用来存储前面$k$个矩形里面一共有多少个点，然后利用二分查找来确定当前的pick_num应该选在哪个矩形里面: idx = BSearch(pick_num + 1) - 1，这里有prefix[idx] <= pick_num，所以应该是在索引为idx的矩形的第pick_num - prefix[idx]个点处（索引从零开始）

代码 链接到标题 

class Solution {
private:
    int total_num = 0;
    int pick_num = 0;
    vector<vector<int>> rectangles;
    vector<int> points_num;
    int BSearch(int target) {
        int left = 0, right = points_num.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (points_num[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
public:
    Solution(vector<vector<int>>& rects) {
        points_num.push_back(0);
        for (auto &vec : rects) {
            rectangles.push_back(vec);
            total_num += (vec[2] - vec[0] + 1) * (vec[3] - vec[1] + 1);
            points_num.push_back(total_num);
        }
    }
    vector<int> pick() {
        int choose = pick_num % total_num;
        int idx = BSearch(choose + 1) - 1; // 选择索引为idx的矩形
        choose -= points_num[idx]; // 从索引为idx的矩形的索引为choose的点
        int x_idx = choose % (rectangles[idx][2] - rectangles[idx][0] + 1); // 对矩形的长取模
        int y_idx = choose / (rectangles[idx][2] - rectangles[idx][0] + 1);
        pick_num++;
        return {x_idx + rectangles[idx][0], y_idx + rectangles[idx][1]};
    }
};