企业官网建设流程全解析

LeetCode-Go 题解：497. Random Point in Non-overlapping Rectangles（前缀和加权抽样 + 二分查找）

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本文基于开源仓库 LeetCode-Go 中 497 题解题文档 及其 Go 实现源码 与配套测试，系统讲解在非重叠轴对齐矩形覆盖空间中均匀随机抽取整数点的完整解法：先按矩形面积加权随机选中一个矩形（前缀和 + 二分查找），再在该矩形内均匀选取整数坐标。读完本文，你将掌握"权重即面积"的带权随机抽样思路、前缀和数组的构建与二分定位技巧，并能直接运行仓库测试验证实现正确性。

题目回顾：在矩形覆盖空间内均匀抽取整数点

给定一个非重叠轴对齐矩形列表rects，要求实现一个Solution类，其pick()方法能够"随机且均匀地"（randomly and uniformly）选取矩形覆盖空间中的整数点。

题目的关键约束（与仓库中 497 题 README 一致）：

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次。

官方输入语法说明：输入由两个列表构成——被调用的子例程列表及其参数列表。Solution构造函数接收矩形数组rects，pick无参数；参数总是以列表形式包裹。

示例输入输出（来自原文档）：

Input: ["Solution","pick","pick","pick"] [[[[1,1,5,5]]],[],[],[]] Output: [null,[4,1],[4,1],[3,3]]

Input: ["Solution","pick","pick","pick","pick","pick"] [[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]] Output: [null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]

注意输出是随机过程，同一输入每次运行结果不同，上述仅为示例输出。

核心思路：为什么"均匀"不能用均匀选矩形实现

一个常见的错误直觉是：先随机选一个矩形，再在矩形内随机选点。但题目要求的是在整个覆盖空间内均匀，而非在矩形间均匀。

以两个矩形为例：假设矩形 A 覆盖 100 个整数点，矩形 B 只覆盖 1 个点。如果先等概率选矩形再选点，那么 B 中唯一的点被选中的概率是1/2，而 A 中每个点被选中的概率只有1/200，这显然破坏了均匀性。

正确的做法是按"点数量"加权选矩形。由于矩形内整数点数量恰为(x2 - x1 + 1) * (y2 - y1 + 1)，即"长度 + 1"乘"宽度 + 1"，所以权重就是矩形可容纳整数点的面积（点格数）。这就是原文档解题思路中所述："这一题是第 528 题的变种题，这一题权重是面积，按权重（面积）选择一个矩形，然后再从矩形中随机选择一个点即可。思路和代码和第 528 题一样。"

整体算法分为两步：

1. 按权重选矩形：用面积构建前缀和数组，随机生成0, 总面积)内的整数，通过二分查找定位到对应矩形；
2. 矩形内均匀选点：把矩形内所有整数点按行展开，用取模与整除运算映射出x与y坐标。

仓库源码解读：前缀和构建

仓库中 [497 题实现 定义了解题结构体：

type Solution497 struct { rects [][]int arr []int }

rects保存原始矩形列表，arr保存前缀和数组。构造函数Constructor497逐个累加面积：

func Constructor497(rects [][]int) Solution497 { s := Solution497{ rects: rects, arr: make([]int, len(rects)), } for i := 0; i < len(rects); i++ { area := (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1) if area < 0 { area = -area } if i == 0 { s.arr[0] = area } else { s.arr[i] = s.arr[i-1] + area } } return s }

几个值得注意的实现细节：

• 面积公式：(x2 - x1 + 1) * (y2 - y1 + 1)。由于边界点也算在内，长度与宽度都需要+1。例如矩形[1,1,5,5]的点数为(5-1+1) * (5-1+1) = 25。
• 负数归一化：if area < 0 { area = -area }处理了坐标顺序异常导致乘积为负的情况（例如测试用例中的{0, 0, -3, 2}）。从测试代码的注释可以看出，这一分支专门用于覆盖area = -area归一化逻辑。
• 前缀和语义：arr[i]表示"前i+1个矩形的累计面积（点数）"，arr[len(arr)-1]即为覆盖空间中整数点的总数。前缀和数组是单调递增的，这正是后续二分查找的前提。

Pick 实现：随机数定位 + 二分查找 + 坐标映射

Pick方法完整代码如下（来自 497 题源码）：

func (so *Solution497) Pick() []int { r := rand.Int() % so.arr[len(so.arr)-1] //get rectangle first // Since r < so.arr[len(so.arr)-1], the binary search always finds an index. low, high, index := 0, len(so.arr)-1, 0 for low <= high { mid := low + (high-low)>>1 if so.arr[mid] > r { if mid == 0 || so.arr[mid-1] <= r { index = mid break } high = mid - 1 } else { low = mid + 1 } } if index > 0 { r = r - so.arr[index-1] } length := so.rects[index][2] - so.rects[index][0] return []int{so.rects[index][0] + r%(length+1), so.rects[index][1] + r/(length+1)} }

逐步拆解：

1. 随机整数定位：r := rand.Int() % total生成[0, total)内的整数，total = so.arr[len(so.arr)-1]。由于r严格小于总面积，二分查找必然能找到一个合法下标，源码注释也明确说明了这一点。

2. 二分查找确定矩形：在前缀和数组arr上二分，找到第一个满足arr[mid] > r且arr[mid-1] <= r的位置，即随机数r落在哪个矩形的面积区间内。low + (high-low)>>1是防溢出的中点写法。

3. 区间内偏移量还原：r = r - so.arr[index-1]把全局随机数转换成"第index个矩形内部的偏移量"，取值范围0, area)。

4. 坐标映射：令length = x2 - x1（注意此处是未加 1 的差值），则

   • x = x1 + r % (length+1)：按列取模，得到矩形内的横坐标偏移；
   • y = y1 + r / (length+1)：按行整除，得到矩形内的纵坐标偏移。

   这相当于把矩形内的所有整数点按行主序（row-major）展开成一维数组，随机偏移量r整除/取模即可均匀落到每个点。由于矩形宽度不超过2000，r / (length+1)不会越出矩形高度范围。

关联题 528：权重抽样的通用模板

原文档明确将本题定位为528 题（Random Pick with Weight）的变种。对比两份源码可以清晰看到同构关系：

• [528. Random Pick with Weight 用Constructor528构建权重前缀和prefixSum，PickIndex用rand.Intn(total) + 1生成随机数，再二分定位第一个大于等于该随机数的下标；
• 497 题只是把 528 的"权重数组"换成了"矩形面积数组"，并在定位矩形后多了一步矩形内坐标展开。

两者的共性模板可抽象为：

构造前缀和数组 prefix（O(n)） 每次抽取： r = rand.Intn(prefix[n-1]) // 或 +1 调整开闭区间 idx = 二分查找第一个满足条件的位置 // O(log n) 返回 idx 对应的实体（下标或矩形内坐标）

rand.Intn（Go 1.20 之前）或rand.Int() % total都要求在0, total)区间均匀取值，二分边界条件（> r与<= r）必须与前缀和的左闭右开语义严格匹配，这是该类题最容易写错的地方。

复杂度与正确性分析

• 时间复杂度：Constructor497为O(n)（n = rects.length <= 100）；每次Pick为O(log n)（二分查找），常数级坐标映射。
• 空间复杂度：O(n)，用于存储前缀和数组。
• 均匀性论证：
  1. 矩形被选中的概率正比于其整数点数量（面积），即第i个矩形被选中的概率为area_i / total；
  2. 选定矩形后，内部整数点按行主序展开并用均匀随机数取模/整除，每个点被选中的概率均等；
  3. 综合两点，任意整数点被选中的概率均为1 / total，满足"uniformly"要求；
  4. 边界点计入：面积公式中+1的项确保了x1、x2及y1、y2所在的行列全部参与映射，边界坐标必然在候选集合内。

测试验证：仓库测试如何保证正确性

仓库为本题提供了配套测试 [497. Random Point in Non-overlapping Rectangles_test.go，覆盖了三条关键路径：

1. 单矩形示例：对[[1,1,5,5]]连续调用 6 次Pick，验证基本调用流程（对应官方 Example 1）；
2. 多矩形命中校验：使用w2 := [][]int{{-2,-2,-1,-1}, {1,0,3,0}, {-2,0,0,5}, {10,10,20,20}}构造实例，循环 200 次调用Pick，每次用辅助函数inAnyRect校验返回点必须落在某个矩形内（inAnyRect对x1 > x2的情况做了交换归一处理，与构造函数中的负数面积归一逻辑呼应）；
3. 负数面积归一化分支：使用w3 := [][]int{{0, 0, -3, 2}}构造实例，断言sol3.arr[0] > 0，确保area = -area分支生效。

运行测试命令（在仓库根目录下）：

go test -v -run Test_Problem497 ./leetcode/0497.Random-Point-in-Non-overlapping-Rectangles/

测试通过即证明实现不会越界、返回点必然位于覆盖空间内，且归一化逻辑正确。

边界情况与易错点小结

• 面积必须 +1：忘记+1会导致边界点（如x2、y2所在行/列）永远无法被选中，破坏均匀性与边界包含要求。
• 随机数区间开闭：rand.Int() % total生成[0, total)，因此二分时使用arr[mid] > r找第一个严格大于r的位置，两者语义必须配套；若改用rand.Intn(total) + 1（528 题写法），二分条件需相应调整。
• 负数坐标与面积：坐标可为负（如[-2,-2,-1,-1]），但面积乘积理论非负；源码额外处理了异常输入导致的负面积，属于防御性写法。
• 宽度上限：题目限定长宽不超过2000，r % (length+1)与r / (length+1)的运算不会溢出int（Go 在 64 位平台int为 64 位，100 * 2000 * 2000量级远在安全范围内）。

与同仓库随机抽样系列题的横向对比

LeetCode-Go 仓库中还有同类"随机均匀采样"题目可对照学习：

• 528. Random Pick with Weight：一维带权下标抽样，497 题的直接前身；
• 478. Generate Random Point in a Circle：在圆内均匀取浮点坐标，采用"拒绝采样"（rejection sampling）：不断在包围正方形内生成(rx, ry)，直到满足x^2 + y^2 <= R^2才返回。其 Go 实现 展示了与 497 题不同的第二类均匀采样策略——当无法直接建立连续均匀映射时，用"生成 + 拒绝"换取均匀性。

对比可见：497 题是离散点格 + 加权前缀和的代表，478 题是连续区域 + 拒绝采样的代表，二者共同构成 LeetCode 随机采样题的两种主流范式。

总结

497. Random Point in Non-overlapping Rectangles 的核心价值在于把"空间均匀采样"问题巧妙地转化为"面积加权抽样"问题：用前缀和数组承载面积权重，用二分查找完成O(log n)的加权选矩形，再用取模/整除在矩形内均匀展开整数点。仓库提供的 完整实现 与 测试用例 可直接作为模板复用：凡是遇到"按权重随机抽取实体，再在实体内部均匀细分"的场景，这套"前缀和 + 二分 + 区间内展开"的组合都是首选方案。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go