二分查找，求解《497. 非重叠矩形中的随机点》
例题
497. 非重叠矩形中的随机点
给定一个由非重叠的轴对齐矩形的数组 rects ，其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点，(xi, yi) 是第 i 个矩形的右上角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被矩形覆盖。所有满足要求的点必须等概率被返回。
在给定的矩形覆盖的空间内的任何整数点都有可能被返回。
请注意 ，整数点是具有整数坐标的点。
实现 Solution 类:
Solution(int[][] rects) 用给定的矩形数组 rects 初始化对象。
int[] pick() 返回一个随机的整数点 [u, v] 在给定的矩形所覆盖的空间内。
答案
二分查找
var Solution = function(rects) {
this.ar = [0]
this.rects = rects
for (let i = 0; i < rects.length; i++) {
const rect = rects[i]
const [x1, y1, x2, y2] = rect
this.ar.push(this.ar[this.ar.length - 1] + (x2 - x1 + 1) * (y2 - y1 + 1))
}
};
Solution.prototype.pick = function() {
const r = Math.random() * this.ar[this.ar.length - 1] | 0
const i = this.upper_bound(this.ar, r + 1) - 1
const rect = this.rects[i]
const [x1, y1, x2] = rect
const sum = r - this.ar[i]
const d = x2 - x1 + 1
return [x1 + (sum % d), y1 + (sum / d | 0)]
};
Solution.prototype.upper_bound = function(nums, num) {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >>> 1
if (nums[m] >= num) r = m - 1
else l = m + 1
}
return l
}class Solution {
ar: number[]
rects: number[][]
constructor(rects: number[][]) {
this.ar = [0]
this.rects = rects
for (let i = 0; i < rects.length; i++) {
this.ar.push(this.ar[this.ar.length - 1] + (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1))
}
}
pick(): number[] {
let sum = Math.random() * this.ar[this.ar.length - 1] | 0
const i = this.upper_bound(this.ar, sum + 1) - 1
const [x1, y1, x2] = this.rects[i]
const d = x2 - x1 + 1
sum -= this.ar[i]
return [x1 + (sum % d), y1 + (sum / d | 0)]
}
upper_bound(nums: number[], num: number): number {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >>> 1
if (nums[m] >= num) r = m - 1
else l = m + 1
}
return l
}
}type Solution struct {
ar []int
rects [][]int
}
func Constructor(rects [][]int) Solution {
ar := make([]int, len(rects) + 1)
for i, rect := range rects {
ar[i + 1] = ar[i] + (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1)
}
return Solution{ar, rects}
}
func (this *Solution) Pick() []int {
n := len(this.ar)
sum := rand.Intn(this.ar[n - 1])
i := sort.SearchInts(this.ar, sum + 1) - 1
sum -= this.ar[i]
r := this.rects[i]
x1, y1, x2 := r[0], r[1], r[2]
d := x2 - x1 + 1
return []int{x1 + sum % d, y1 + sum / d}
}class Solution {
List<Integer> ar;
Random rand;
int[][] rs;
public Solution(int[][] rects) {
ar = new ArrayList<Integer>();
rand = new Random();
rs = rects;
ar.add(0);
for (int i = 0; i < rects.length; i++) {
ar.add(ar.get(ar.size() - 1) + (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1));
}
}
public int[] pick() {
int r = rand.nextInt(ar.get(ar.size() - 1));
int i = upper_bound(ar, r + 1) - 1;
int sum = r - ar.get(i);
int[] rect = rs[i];
int x1 = rect[0], y1 = rect[1], x2 = rect[2];
int d = x2 - x1 + 1;
return new int[]{x1 + (sum % d), y1 + (sum / d)};
}
public int upper_bound(List<Integer> nums, int num) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int m = l + r >>> 1;
if (nums.get(m) >= num) r = m - 1;
else l = m + 1;
}
return l;
}
}