Skip to content

Latest commit

 

History

History
101 lines (76 loc) · 3.38 KB

497-random-point-in-non-overlapping-rectangles.md

File metadata and controls

101 lines (76 loc) · 3.38 KB

497. Random Point in Non-overlapping Rectangles - 非重叠矩形中的随机点

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

提示:

  1. 整数点是具有整数坐标的点。
  2. 矩形周边上的点包含在矩形覆盖的空间中。
  3. i 个矩形 rects [i] = [x1,y1,x2,y2],其中 [x1,y1] 是左下角的整数坐标,[x2,y2] 是右上角的整数坐标。
  4. 每个矩形的长度和宽度不超过 2000。
  5. 1 <= rects.length <= 100
  6. pick 以整数坐标数组 [p_x, p_y] 的形式返回一个点。
  7. 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 的构造函数有一个参数,即矩形数组 rectspick 没有参数。参数总是用列表包装的,即使没有也是如此。

 


题目标签:Binary Search / Random

题目链接:LeetCode / LeetCode中国

题解

TIM图片20190407112406

Language Runtime Memory
java 109 ms 47.7 MB
class Solution {
    List<Integer> S = new ArrayList<>();
    int[][] rects;

    public Solution(int[][] rects) {
        this.rects = rects;
        // 记录每个矩形包含的点数的累加和数组
        int tmp = 0;
        for (int[] r : rects) {
            tmp += (r[2] - r[0] + 1) * (r[3] - r[1] + 1);
            S.add(tmp);
        }
    }

    public int[] pick() {
        // 选择一个点编号
        int num = (int)(Math.random() * S.get(S.size() - 1) + 1);
        // 确定位于哪个矩形
        int l = 0, r = S.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (S.get(mid) >= num) r = mid;
            else l = mid + 1;
        }
        // 计算点编号对应的点坐标
        int x = rects[l][0] + (S.get(l) - num) % (rects[l][2] - rects[l][0] + 1);
        int y = rects[l][1] + (S.get(l) - num) / (rects[l][2] - rects[l][0] + 1);
        return new int[]{x, y};
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(rects);
 * int[] param_1 = obj.pick();
 */