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

2023-11-30 HGNULB 约 13 分钟

文章信息 6 个分类 7 个标签

分类

题目描述

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

题意分析

题目目标：给定一组互不重叠的轴对齐矩形，每个矩形用左下角和右上角的整数坐标描述，要求实现一个 pick 方法，从所有矩形覆盖的整数点中等概率地随机返回一个点。
核心约束：「等概率」这三个字是全部难点所在——它要求的不是「先等概率选一个矩形、再在矩形内等概率选一个点」，因为矩形大小不同，那样会让小矩形里的点被选中的概率远高于大矩形里的点。真正的要求是所有候选点作为一个整体等概率，因此选矩形时必须按它包含的点数加权。第二个信号是矩形边界闭合且坐标是整数，所以一个矩形包含的点数是 $(x_2-x_1+1)\times(y_2-y_1+1)$，两个方向上都要加一。第三个信号是矩形互不重叠，这保证了不同矩形的点集不相交，总点数就是各矩形点数之和，不需要做容斥。第四个是 pick 会被调用很多次而矩形集合固定不变，典型的「一次预处理、多次查询」结构。
边界处理：矩形可能退化成一条线段甚至一个点（宽或高为 1），点数公式的加一必须保留；坐标范围到 $\pm 10^9$，但题目保证覆盖的整数点总数在可控范围内；随机数的取值区间与前缀和数组的下标基准要严格对齐，差一就会让第一个点或最后一个点永远取不到；把线性偏移还原成二维坐标时，除数与模数分别对应哪一个维度必须与编号时的约定一致。

解法：前缀面积 + 二分采样

核心思路

先看两种错误的直觉。第一种是先在 n 个矩形里等概率挑一个，再在其中等概率挑一个点。这显然不对：一个只含 1 个点的矩形和一个含 100 个点的矩形被选中的概率相同，那么前者那个点的概率是后者每个点的一百倍。第二种是把所有整数点全部枚举出来存进数组再随机下标，逻辑上完全正确，但坐标范围到 $10^9$，点数可能上亿，内存与预处理时间都不可接受。
正确的思路来自一个视角转换：把所有矩形里的点想象成排成一条长队，依次编号 1 到 total。第 1 个矩形的点占据编号 1 到 $c_1$，第 2 个矩形的点占据 $c_1+1$ 到 $c_1+c_2$，依此类推。既然编号是连续且不重复的，那么「在所有点中等概率抽一个」就等价于「在 1 到 total 中等概率抽一个整数 k」——这一步把二维的加权采样彻底压平成了一维的均匀采样，而后者只需要一次随机数调用。
抽到编号 k 之后要做的是把它翻译回具体的点，这分两层。第一层是定位它属于哪个矩形：如果预先算好每个矩形的点数前缀和 prefix[i]（表示前 i+1 个矩形的点数总和），那么 k 所属的矩形就是第一个满足 prefix[i] >= k 的下标 i。由于前缀和严格递增，这个查询正是有序数组上的「找下界」，可以用二分在 $O(\log n)$ 内完成。第二层是在矩形内部定位：先算出 k 在这个矩形内部的相对偏移 offset = k - 前一个前缀和 - 1，让它落在 0 到「该矩形点数减一」之间，再把这个一维偏移按行列展开成二维坐标。
因此维护的状态很简单：一个严格递增的前缀和数组 prefix，以及总点数 total。不变量是 prefix[i] 恒等于前 i+1 个矩形包含的整数点总数，这个不变量既支撑了二分的正确性，也提供了计算内部偏移所需的基准。

点数、前缀和和随机编号统一使用 64 位。Java 的 nextLong(total) 与 Go 的 rand.Int63n(total) 都接收 64 位正上界并均匀返回 [0,total)；再加 1 得到 [1,total]。不要把 total 强转成 32 位，也不要用随机整数取模代替有界 API，否则会溢出或产生模偏差。

解题步骤

第一步：构造函数中遍历所有矩形，用 $(x_2-x_1+1)\times(y_2-y_1+1)$ 算出每个矩形的点数，累加进 total 并把当前累计值写入 prefix[i]。 为什么两个方向都要加一：边界是闭区间，从 $x_1$ 到 $x_2$ 一共有 $x_2-x_1+1$ 个整数，漏掉加一会让每个矩形都少算一整行和一整列，退化矩形甚至会算出 0 个点。为什么把预处理放进构造函数：矩形集合固定不变而 pick 会被反复调用，把 $O(n)$ 的工作前置一次，每次调用就只剩 $O(\log n)$。

第二步：pick 中生成 [1,total] 内的 64 位随机编号 k。 Java 用 ThreadLocalRandom.current().nextLong(total) + 1，Go 用 rand.Int63n(total) + 1；两个有界 API 的参数都必须为正，本题每个闭矩形至少含一个格点，所以 total > 0。

第三步：在 prefix 上二分找第一个不小于 k 的位置。 为什么是「不小于」而非「大于」：k 恰好等于某个 prefix[i] 时，它是第 i 个矩形的最后一个点，仍然属于该矩形；用严格大于会把它推给下一个矩形，导致每个矩形的最后一个点被错误归属，最后一个矩形的最后一个点甚至会让下标越界。为什么二分成立：矩形点数都是正数，所以 prefix 严格递增，「不小于 k」这个性质在数组上呈单调分界。

第四步：算出该矩形的起始基准 base（下标为 0 时取 0，否则取 prefix[idx-1]），再求 offset = k - base - 1。 为什么要减一：k 是从 1 开始的编号，而 offset 需要从 0 开始才能做除法和取模；k - base 落在 1 到点数之间，再减一才落到 0 到点数减一。为什么下标为 0 时基准取 0：第一个矩形前面没有任何矩形，累计量为 0。

第五步：把 offset 展开成坐标，x = x_1 + offset / h、y = y_1 + offset % h，其中 h 是矩形的高度（纵向点数）。 为什么用高度作除数：这等价于约定「按列优先给矩形内的点编号」——每 h 个连续编号构成一列，商给出第几列（对应 x 的偏移），余数给出列内第几行（对应 y 的偏移）。为什么不能除以宽度：那对应的是按行优先编号，此时商应当加到 y 上、余数加到 x 上；除数和加法对象必须成对匹配，交叉搭配会让点落到矩形之外。为什么这个映射是双射：offset 的取值恰好是 0 到 $w \times h - 1$，商覆盖 0 到 $w-1$、余数覆盖 0 到 $h-1$，每个 (商, 余数) 组合对应唯一的 offset，因此矩形内每个点被取到的概率完全相同。

以 rects = [[-2,-2,-1,-1],[1,0,3,0]] 走一遍。 两个矩形分别含 4、3 个点，故 prefix = [4,7]。若有界随机 API 返回 4，加一后 k = 5，二分定位第二个矩形，base = 4、offset = 0，映射为 (1,0)；若 k = 4，应仍归入第一个矩形并映射为 (-1,-1)，这验证了二分条件必须包含等号。

代码实现

import java.util.concurrent.ThreadLocalRandom;

// 核心实现：前缀面积 + 二分采样，维护必要状态并避免重复处理。
class Solution {
    private final int[][] rects;
    private final long[] prefix;
    private final long total;

    public Solution(int[][] rects) {
        this.rects = rects;
        this.prefix = new long[rects.length];
        long count = 0;
        for (int i = 0; i < rects.length; i++) {
            int[] r = rects[i];
            long width = (long) r[2] - r[0] + 1;
            long height = (long) r[3] - r[1] + 1;
            count += width * height;
            prefix[i] = count;
        }
        this.total = count;
    }

    public int[] pick() {
        long k = ThreadLocalRandom.current().nextLong(total) + 1;
        int idx = lowerBound(prefix, k);
        int[] r = rects[idx];
        long height = (long) r[3] - r[1] + 1;

        long base = idx == 0 ? 0 : prefix[idx - 1];
        long offset = k - base - 1;
        int x = (int) (r[0] + offset / height);
        int y = (int) (r[1] + offset % height);
        return new int[]{x, y};
    }

    private int lowerBound(long[] arr, long target) {
        int l = 0;
        int r = arr.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (arr[m] >= target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

import "math/rand"

// 核心实现：前缀面积 + 二分采样，维护必要状态并避免重复处理。
type Solution struct {
	rects  [][]int
	prefix []int64
	total  int64
}

func Constructor(rects [][]int) Solution {
	prefix := make([]int64, len(rects))
	var total int64
	for i, r := range rects {
		width := int64(r[2]) - int64(r[0]) + 1
		height := int64(r[3]) - int64(r[1]) + 1
		total += width * height
		prefix[i] = total
	}
	return Solution{rects: rects, prefix: prefix, total: total}
}

func (this *Solution) Pick() []int {
	k := rand.Int63n(this.total) + 1
	idx := lowerBound(this.prefix, k)
	r := this.rects[idx]
	height := int64(r[3]) - int64(r[1]) + 1

	var base int64
	if idx > 0 {
		base = this.prefix[idx-1]
	}
	offset := k - base - 1
	x := r[0] + int(offset/height)
	y := r[1] + int(offset%height)
	return []int{x, y}
}

func lowerBound(arr []int64, target int64) int {
	l, r := 0, len(arr)
	for l < r {
		m := l + (r-l)/2
		if arr[m] >= target {
			r = m
		} else {
			l = m + 1
		}
	}
	return l
}

复杂度分析

时间复杂度：构造函数 $O(n)$，单次 pick 为 $O(\log n)$，n 为矩形个数。凭什么：构造时每个矩形只做常数次算术并写一次前缀和；每次采样只有一次随机数生成、一次在长度为 n 的有序数组上的二分、以及常数次除法取模，与矩形覆盖的点数完全无关。

空间复杂度：$O(n)$。凭什么：额外结构只有长度为 n 的前缀和数组和几个标量，矩形数组是输入本身；关键在于没有把任何一个整数点物化出来，否则空间会随覆盖面积爆炸。

关键点总结

按权重随机的通用套路是「前缀和 + 均匀采样 + 二分定位」：把每个候选的权重摊成数轴上一段长度与之成正比的区间，在总长度上均匀掷一个点，落在哪段就选哪个。这个模板同时适用于按权重选下标、按面积选矩形、按频次选元素等一大类问题。

等概率的正确定义是「对最终的原子对象等概率」，而不是「对分组等概率」。看到分组大小不一致时，第一反应就该是加权而非两级均匀，这是随机化设计题最高频的错误来源。

把二维采样降成一维是核心手法：先用一个线性编号唯一标识每个点，采样在编号空间完成，最后再用除法与取模把编号还原成坐标。降维的前提是编号与点之间构成双射，还原时除数与加法对象必须与编号时的行列约定严格对应。

闭区间的点数是「右减左加一」。这个加一在退化成线段或单点的矩形上尤其致命，漏掉会直接算出 0 个点导致该矩形永远取不到甚至除零。

随机数区间与前缀和基准必须整体对齐。要么用 1 到 total 的编号配「找第一个不小于 k」，要么用 0 到 total-1 的编号配「找第一个大于 k」，两套写法各自自洽，混搭必然差一。

有界 64 位随机 API 会处理拒绝采样，保证每个编号等概率；直接用 random % total 只有在随机源范围恰好整除 total 时才无偏。

面试视角：这题是设计题里的常客，面试官会先问「为什么不能先等概率选矩形」，再问「如何保证每个点等概率」，最后问复杂度。回答时要主动画出「所有点排成一条长队」这个心智模型，它能让加权采样、前缀和、二分三者的关系一句话讲清。常见追问是「如果矩形会动态增删怎么办」（前缀和失效，需要换成树状数组维护可变权重）以及「如果内存不允许存前缀和呢」（可以改用水塘抽样，一次遍历、$O(1)$ 额外空间，但每次采样退化成 $O(n)$）。

易错点总结

错误写法：先 rand.nextInt(n) 等概率选矩形，再在矩形内均匀取点。用例 rects = [[0,0,0,0],[0,1,9,10]] → 第一个矩形只有 1 个点却占一半概率，而第二个矩形的 100 个点分摊另一半，单点概率相差百倍，无法通过概率校验。

错误写法：点数算成 $(x_2-x_1)\times(y_2-y_1)$，漏掉加一。用例 rects = [[1,0,3,0]] → 高度算成 0，点数为 0，total 为 0，nextInt(0) 抛 IllegalArgumentException。

错误写法：二分条件写成 prefix[m] > target。用例 rects = [[-2,-2,-1,-1],[1,0,3,0]] 且 k = 4 → 第一个矩形的最后一个点被判给第二个矩形，offset 算出负数，坐标落到矩形之外；若 k 恰好等于 total 还会让二分返回 n 导致数组越界。

错误写法：随机数写成 rand.nextInt(total) 却仍用「找第一个不小于 k」的二分。用例 rects = [[0,0,0,0],[1,1,1,1]] → k 可能取到 0，二分返回 0，offset 算成 -1，坐标错误；同时最后一个点永远取不到。

错误写法：内部偏移忘记减一，写成 offset = k - base。用例单个 1×1 矩形 [[0,0,0,0]] → offset 变成 1 而点数只有 1，除法商为 1，x 越出矩形右边界。

错误写法：展开坐标时用宽度作除数却仍把商加到 x 上。用例 rects = [[0,0,2,1]]（宽 3 高 2，共 6 点）→ offset 为 3 时商为 1、余数为 0，得到 (1, 0)；而 offset 为 4 时商为 1、余数为 1，得到 (1, 1)，看似正常，但 offset 为 5 时商为 1、余数为 2，y 变成 2 超出上边界 1，点落在矩形外。

错误写法：把商和余数的加法对象写反，x = x1 + offset % h、y = y1 + offset / h。用例 rects = [[0,0,2,1]] → offset 为 5 时 x 得 0 + 1 = 1、y 得 0 + 2 = 2，y 越界。

错误写法：把 prefix 定义成「不含当前矩形的累计值」却仍按「含当前」的方式二分。用例任意多矩形输入 → 整体偏移一个矩形，最后一个矩形永远取不到，第一个矩形被过度采样。

错误写法：每次 pick 都重新计算前缀和。用例大量调用 pick → 单次退化成 $O(n)$，在调用次数达到 $10^4$ 且矩形数为 100 时白白多出百万次运算，且完全没有必要。

错误写法：total 用 32 位整数存储。覆盖点数超过 $2^{31}-1$ 时累计值溢出，随机范围和二分都会失效；前缀和与随机编号必须使用 64 位。

错误写法：先生成任意随机整数再 % total。随机源取值个数通常不是 total 的整数倍，余数分布会有模偏差，无法保证格点严格等概率。

错误写法：用 (long) (Math.random() * total) 生成超大范围编号。double 只有 53 位有效整数精度，total 很大时部分编号不可达或权重不均；应直接使用有界的 64 位整数随机 API。

相似题目

题目	难度	考察点
528. 按权重随机选择	中等	同一套前缀和加二分模板的一维原型，去掉了二维坐标还原这一层
LCR 071. 按权重随机选择	中等	与 528 同题，可用来对照不同的随机数区间与二分条件搭配写法
478. 在圆内随机生成点	中等	连续区域的均匀采样，需要对半径做平方根变换才能避免向圆心聚集
398. 随机数索引	中等	用水塘抽样在一次遍历中等概率选出目标下标，是本题在内存受限时的替代方案
380. O(1) 时间插入、删除和获取随机元素	中等	集合动态可变时的等概率采样，靠数组加哈希表维持随机访问
710. 黑名单中的随机数	困难	在有空洞的值域上等概率采样，用映射把黑名单位置重定向到尾部合法区间