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 一致整数点指坐标均为整数的点矩形边界上的点也属于覆盖空间即边界点必须可能被选到第i个矩形表示为rects[i] [x1, y1, x2, y2]其中[x1, y1]是左下角整数坐标[x2, y2]是右上角整数坐标每个矩形的长度和宽度均不超过20001 rects.length 100pick返回整数坐标数组[p_x, p_y]pick最多被调用10000次。官方输入语法说明输入由两个列表构成——被调用的子例程列表及其参数列表。Solution构造函数接收矩形数组rectspick无参数参数总是以列表形式包裹。示例输入输出来自原文档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 题一样。整体算法分为两步按权重选矩形用面积构建前缀和数组随机生成0, 总面积)内的整数通过二分查找定位到对应矩形矩形内均匀选点把矩形内所有整数点按行展开用取模与整除运算映射出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-11) * (5-11) 25。负数归一化if area 0 { area -area }处理了坐标顺序异常导致乘积为负的情况例如测试用例中的{0, 0, -3, 2}。从测试代码的注释可以看出这一分支专门用于覆盖area -area归一化逻辑。前缀和语义arr[i]表示前i1个矩形的累计面积点数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%(length1), so.rects[index][1] r/(length1)} }逐步拆解随机整数定位r : rand.Int() % total生成[0, total)内的整数total so.arr[len(so.arr)-1]。由于r严格小于总面积二分查找必然能找到一个合法下标源码注释也明确说明了这一点。二分查找确定矩形在前缀和数组arr上二分找到第一个满足arr[mid] r且arr[mid-1] r的位置即随机数r落在哪个矩形的面积区间内。low (high-low)1是防溢出的中点写法。区间内偏移量还原r r - so.arr[index-1]把全局随机数转换成第index个矩形内部的偏移量取值范围0, area)。坐标映射令length x2 - x1注意此处是未加 1 的差值则x x1 r % (length1)按列取模得到矩形内的横坐标偏移y y1 r / (length1)按行整除得到矩形内的纵坐标偏移。这相当于把矩形内的所有整数点按行主序row-major展开成一维数组随机偏移量r整除/取模即可均匀落到每个点。由于矩形宽度不超过2000r / (length1)不会越出矩形高度范围。关联题 528权重抽样的通用模板原文档明确将本题定位为528 题Random Pick with Weight的变种。对比两份源码可以清晰看到同构关系[528. Random Pick with Weight 用Constructor528构建权重前缀和prefixSumPickIndex用rand.Intn(total) 1生成随机数再二分定位第一个大于等于该随机数的下标497 题只是把 528 的权重数组换成了矩形面积数组并在定位矩形后多了一步矩形内坐标展开。两者的共性模板可抽象为构造前缀和数组 prefixO(n) 每次抽取 r rand.Intn(prefix[n-1]) // 或 1 调整开闭区间 idx 二分查找第一个满足条件的位置 // O(log n) 返回 idx 对应的实体下标或矩形内坐标rand.IntnGo 1.20 之前或rand.Int() % total都要求在0, total)区间均匀取值二分边界条件 r与 r必须与前缀和的左闭右开语义严格匹配这是该类题最容易写错的地方。复杂度与正确性分析时间复杂度Constructor497为O(n)n rects.length 100每次Pick为O(log n)二分查找常数级坐标映射。空间复杂度O(n)用于存储前缀和数组。均匀性论证矩形被选中的概率正比于其整数点数量面积即第i个矩形被选中的概率为area_i / total选定矩形后内部整数点按行主序展开并用均匀随机数取模/整除每个点被选中的概率均等综合两点任意整数点被选中的概率均为1 / total满足uniformly要求边界点计入面积公式中1的项确保了x1、x2及y1、y2所在的行列全部参与映射边界坐标必然在候选集合内。测试验证仓库测试如何保证正确性仓库为本题提供了配套测试 [497. Random Point in Non-overlapping Rectangles_test.go覆盖了三条关键路径单矩形示例对[[1,1,5,5]]连续调用 6 次Pick验证基本调用流程对应官方 Example 1多矩形命中校验使用w2 : [][]int{{-2,-2,-1,-1}, {1,0,3,0}, {-2,0,0,5}, {10,10,20,20}}构造实例循环 200 次调用Pick每次用辅助函数inAnyRect校验返回点必须落在某个矩形内inAnyRect对x1 x2的情况做了交换归一处理与构造函数中的负数面积归一逻辑呼应负数面积归一化分支使用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) 1528 题写法二分条件需相应调整。负数坐标与面积坐标可为负如[-2,-2,-1,-1]但面积乘积理论非负源码额外处理了异常输入导致的负面积属于防御性写法。宽度上限题目限定长宽不超过2000r % (length1)与r / (length1)的运算不会溢出intGo 在 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解：497. Random Point in Non-overlapping Rectangles（前缀和加权抽样 + 二分查找）
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 一致整数点指坐标均为整数的点矩形边界上的点也属于覆盖空间即边界点必须可能被选到第i个矩形表示为rects[i] [x1, y1, x2, y2]其中[x1, y1]是左下角整数坐标[x2, y2]是右上角整数坐标每个矩形的长度和宽度均不超过20001 rects.length 100pick返回整数坐标数组[p_x, p_y]pick最多被调用10000次。官方输入语法说明输入由两个列表构成——被调用的子例程列表及其参数列表。Solution构造函数接收矩形数组rectspick无参数参数总是以列表形式包裹。示例输入输出来自原文档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 题一样。整体算法分为两步按权重选矩形用面积构建前缀和数组随机生成0, 总面积)内的整数通过二分查找定位到对应矩形矩形内均匀选点把矩形内所有整数点按行展开用取模与整除运算映射出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-11) * (5-11) 25。负数归一化if area 0 { area -area }处理了坐标顺序异常导致乘积为负的情况例如测试用例中的{0, 0, -3, 2}。从测试代码的注释可以看出这一分支专门用于覆盖area -area归一化逻辑。前缀和语义arr[i]表示前i1个矩形的累计面积点数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%(length1), so.rects[index][1] r/(length1)} }逐步拆解随机整数定位r : rand.Int() % total生成[0, total)内的整数total so.arr[len(so.arr)-1]。由于r严格小于总面积二分查找必然能找到一个合法下标源码注释也明确说明了这一点。二分查找确定矩形在前缀和数组arr上二分找到第一个满足arr[mid] r且arr[mid-1] r的位置即随机数r落在哪个矩形的面积区间内。low (high-low)1是防溢出的中点写法。区间内偏移量还原r r - so.arr[index-1]把全局随机数转换成第index个矩形内部的偏移量取值范围0, area)。坐标映射令length x2 - x1注意此处是未加 1 的差值则x x1 r % (length1)按列取模得到矩形内的横坐标偏移y y1 r / (length1)按行整除得到矩形内的纵坐标偏移。这相当于把矩形内的所有整数点按行主序row-major展开成一维数组随机偏移量r整除/取模即可均匀落到每个点。由于矩形宽度不超过2000r / (length1)不会越出矩形高度范围。关联题 528权重抽样的通用模板原文档明确将本题定位为528 题Random Pick with Weight的变种。对比两份源码可以清晰看到同构关系[528. Random Pick with Weight 用Constructor528构建权重前缀和prefixSumPickIndex用rand.Intn(total) 1生成随机数再二分定位第一个大于等于该随机数的下标497 题只是把 528 的权重数组换成了矩形面积数组并在定位矩形后多了一步矩形内坐标展开。两者的共性模板可抽象为构造前缀和数组 prefixO(n) 每次抽取 r rand.Intn(prefix[n-1]) // 或 1 调整开闭区间 idx 二分查找第一个满足条件的位置 // O(log n) 返回 idx 对应的实体下标或矩形内坐标rand.IntnGo 1.20 之前或rand.Int() % total都要求在0, total)区间均匀取值二分边界条件 r与 r必须与前缀和的左闭右开语义严格匹配这是该类题最容易写错的地方。复杂度与正确性分析时间复杂度Constructor497为O(n)n rects.length 100每次Pick为O(log n)二分查找常数级坐标映射。空间复杂度O(n)用于存储前缀和数组。均匀性论证矩形被选中的概率正比于其整数点数量面积即第i个矩形被选中的概率为area_i / total选定矩形后内部整数点按行主序展开并用均匀随机数取模/整除每个点被选中的概率均等综合两点任意整数点被选中的概率均为1 / total满足uniformly要求边界点计入面积公式中1的项确保了x1、x2及y1、y2所在的行列全部参与映射边界坐标必然在候选集合内。测试验证仓库测试如何保证正确性仓库为本题提供了配套测试 [497. Random Point in Non-overlapping Rectangles_test.go覆盖了三条关键路径单矩形示例对[[1,1,5,5]]连续调用 6 次Pick验证基本调用流程对应官方 Example 1多矩形命中校验使用w2 : [][]int{{-2,-2,-1,-1}, {1,0,3,0}, {-2,0,0,5}, {10,10,20,20}}构造实例循环 200 次调用Pick每次用辅助函数inAnyRect校验返回点必须落在某个矩形内inAnyRect对x1 x2的情况做了交换归一处理与构造函数中的负数面积归一逻辑呼应负数面积归一化分支使用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) 1528 题写法二分条件需相应调整。负数坐标与面积坐标可为负如[-2,-2,-1,-1]但面积乘积理论非负源码额外处理了异常输入导致的负面积属于防御性写法。宽度上限题目限定长宽不超过2000r % (length1)与r / (length1)的运算不会溢出intGo 在 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考