侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【随机化, 水塘抽样】非重叠矩形中的随机点

GabrielxD
2022-06-09 / 0 评论 / 0 点赞 / 287 阅读 / 883 字
温馨提示:
本文最后更新于 2022-07-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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


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

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

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

实现 Solution 类:

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

示例 1:

image-20220609032413134

输入: 
["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 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 次。

解题

方法一:水塘抽样

思路

总体思路:现在所有矩形中随机抽出一个矩形,再在该矩形中随机抽出 x、y 坐标即可。

随机抽出矩形:

  • 假设共有 n 个矩形,那么其中某个矩形 k 被选中的概率并不是 1n\frac{1}{n}
  • 而是 Ski=0n1Si\frac{S_k}{\sum\limits _{i=0}^{n-1} S_{i}} 也即 矩形k的面积所有矩形的面积和\frac{矩形 k 的面积}{所有矩形的面积和}

这里我们遍历 rects 数组,维护一个被抽到的矩形下标 idx ,一个总面积 total

  • 对于每个矩形算出其面积 Si=(xiai+1)(yibi+1)S_i=(x_i-a_i+1) * (y_i-b_i+1) (curr)
  • 然后把面积加入到总面积中 total += curr
  • 如果 random[0,total)[0,curr)random[0, total)\in[0, curr) 那么就随机到了当前遍历到的矩形,把 idx 置为当前矩形的索引
  • 由于每次遍历都会抽取矩形,那么这次遍历抽取到的矩形被保留的概率就是 currtotal\frac{curr}{total}

完成遍历后一定可以随机的选出一个矩形 rects[idx]

取出该矩形左下角的点 (a,b)(a, b),右上角的点 (x,y)(x, y)

返回 {random[a,x],random(b,y)]}\{random[a, x], random(b, y)]\}

代码

class Solution {
    private Random rand;
    private int[][] rects;

    public Solution(int[][] _rects) {
        rand = new Random();
        rects = _rects;
    }
    
    public int[] pick() {
        int idx = -1, total = 0;
        for (int i = 0; i < rects.length; i++) {
            int curr = (rects[i][2] - rects[i][0] + 1) *
                (rects[i][3] - rects[i][1] + 1);
            total += curr;
            if (rand.nextInt(total) < curr) idx = i;
        }
        int[] rect = rects[idx];
        int a = rect[0], b = rect[1], x = rect[2], y = rect[3];
        return new int[]{a + rand.nextInt(x - a + 1), b + rand.nextInt(y - b + 1)};
    }
}
0

评论区