LeetCode LCR 071. 按权重随机选择
目录
题目描述
题意分析
给一个正整数权重数组
w，实现pickIndex()，让它返回下标i的概率恰好是w[i] / sum(w)。这是一道把概率问题转成区间问题的设计题。要求的是「按权重成比例地抽样」，而语言内置的随机源只能提供「在一段整数区间上均匀抽样」。两者之间的桥梁就是：把长度为
sum(w)的整数区间按权重切成 $n$ 段，第i段的长度是w[i]，那么均匀落点落进第i段的概率天然就是w[i] / sum(w)。于是
pickIndex的实际任务变成：均匀抽一个落点，然后回答「它落在第几段」。后者是一个查找问题，而段的边界由前缀和给出且天然有序，正好用二分。约束里
w的长度可达 $10^4$、pickIndex的调用次数可达 $10^4$，权重之和可达 $10^8$。这说明：预处理可以是 $O(n)$，但单次查询必须做到 $O(\log n)$；而按权重把下标展开成一个长度为sum(w)的大数组则会占用 $10^8$ 级内存，不可行。边界上要注意：权重全为正，不存在长度为 0 的段，所以每个下标都有非零概率；数组长度可能为 1，此时永远返回 0；随机落点的取值范围必须严格覆盖
[1, sum]或[0, sum-1]，多一个少一个都会让首尾两段的概率失真。
解法：二分查找判定答案
核心思路
最朴素的做法是把下标按权重展开：
w = [2, 3]就构造数组[0, 0, 1, 1, 1]，然后均匀随机取一个位置返回其中的值。概率完全正确，pickIndex也只要 $O(1)$，但空间是 $O(\sum w)$，在权重和达到 $10^8$ 时直接爆内存。瓶颈在于它把「每一份权重」都物化成了一个数组元素，而实际上同一个下标占据的是一段连续区间，完全不必逐格存储，只需记住每段的端点。
观察到：若令
presum[i]表示前i个权重之和（presum[0] = 0），那么下标i对应的区间就是(presum[i], presum[i+1]]，长度恰好是w[i]。这些区间首尾相接、覆盖[1, sum]且互不重叠——这正是一个完整的划分。于是抽样过程分两步：先在
[1, sum]上均匀取一个整数x，再找出唯一满足presum[i] < x <= presum[i+1]的i。由于presum严格递增（权重全正），这个i等价于「第一个满足presum[i+1] >= x的i」，也就是一个标准的左边界二分。维持的不变量是：答案始终落在
[left, right]内；left左侧的所有下标其区间上界都小于x（落点在它们右边），right及其右侧的下标其区间上界都不小于x。判定为真时保留mid（right = mid），为假时排除（left = mid + 1），收敛后的left即为落点所属的段。概率的正确性由此闭合：
x均匀落在[1, sum]的sum个整数上，其中恰有w[i]个会被二分归到下标i，故P(i) = w[i] / sum。
解题步骤
- 构造函数中一次性算好前缀和数组，长度取 $n + 1$，
presum[0] = 0、presum[i+1] = presum[i] + w[i]。多留一个 0 作为哨兵，可以让每段的表达式统一成(presum[i], presum[i+1]]，省掉对第 0 段的特判。- 预处理放在构造函数而不是
pickIndex里。pickIndex会被调用上万次，把 $O(n)$ 的累加摊到每次查询上就变成了 $O(n)$ 单次代价，白白浪费了「一次建表多次查询」的结构。- 每次
pickIndex先取随机落点x，范围是[1, sum]，其中sum = presum[n-1]（数组末元素）。取[1, sum]的闭区间是为了与「段的右端点」对齐，落点为presum[i+1]时应当归属下标i。- 在下标区间
[0, n-2]上二分（此处n是前缀和数组的长度，故实际下标上界是w.length - 1）。判定条件是presum[mid + 1] >= x，即「第mid段的右端点是否已经够到落点」。- 判定为真时
right = mid，因为mid自己就可能是答案；为假时left = mid + 1，因为第mid段整段都在落点左侧，绝无可能。- 循环条件
left < right，退出时left == right，直接返回left，就是落点所在的段号，也就是要抽中的下标。以
w = [1, 3]走一遍：构造时presum = [0, 1, 4]，总权重 4，二分范围是下标[0, 1]。若随机落点x = 1：mid = 0，判定presum[1] = 1 >= 1为真，right = 0，left == right == 0，返回 0。若x = 2：mid = 0，presum[1] = 1 >= 2为假，第 0 段整段在落点左侧，left = 1，返回 1。若x = 3或x = 4：同理均返回 1。四个等概率的落点里，只有x = 1归到下标 0，另外三个归到下标 1，于是P(0) = 1/4、P(1) = 3/4，与权重比 1 : 3 完全一致。
代码实现
class Solution {
private int[] presum;
public Solution(int[] w) {
int n = w.length;
presum = new int[n + 1];
for (int i = 0; i < n; ++i) {
presum[i + 1] = presum[i] + w[i];
}
}
public int pickIndex() {
int n = presum.length;
int x = (int) (Math.random() * presum[n - 1]) + 1;
int left = 0, right = n - 2;
while (left < right) {
int mid = (left + right) >> 1;
if (presum[mid + 1] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
type Solution struct {
presum []int
}
func Constructor(w []int) Solution {
n := len(w)
pre := make([]int, n+1)
for i := 0; i < n; i++ {
pre[i+1] = pre[i] + w[i]
}
return Solution{pre}
}
func (this *Solution) PickIndex() int {
n := len(this.presum)
x := rand.Intn(this.presum[n-1]) + 1
left, right := 0, n-2
for left < right {
mid := (left + right) >> 1
if this.presum[mid+1] >= x {
right = mid
} else {
left = mid + 1
}
}
return left
}
复杂度分析
- 时间复杂度：构造函数 $O(n)$，一次线性累加得到前缀和；
pickIndex单次 $O(\log n)$，一次随机取值加一轮左边界二分，与权重的绝对大小无关。- 空间复杂度：$O(n)$，只存了长度为 $n + 1$ 的前缀和数组，避免了按权重展开所需的 $O(\sum w)$ 空间。
关键点总结
- 「按权重抽样」的通用转化是「把权重铺成连续区间，再对均匀落点做区间定位」。这一步转化把概率问题变成纯粹的查找问题，之后就没有随机性可言了。
- 前缀和把「每份权重占一格」压缩成「每段只记两个端点」，是从 $O(\sum w)$ 空间降到 $O(n)$ 的关键；同时它天然递增，直接为二分提供了有序性。
- 落点区间与段区间必须严格对齐。用左开右闭的段配
[1, sum]的落点，或用左闭右开的段配[0, sum-1]的落点，两套都对，但不能混用，否则首尾两段的概率会偏移。- 一次预处理、多次查询是设计类题目的常见结构。判断哪些计算该放构造函数、哪些放查询接口，依据是「查询次数量级」。
- 二分求的是「第一个右端点不小于落点的段」，仍然是标准左边界模板：满足条件保留
mid，不满足排除mid。判据换了，规则不变。- 面试视角：正确性论证要主动说出来——「
x在sum个整数上均匀分布，落进第i段的整数恰好有w[i]个，故概率为w[i]/sum」。随机化题目里，能把概率算清楚比写出代码更能体现水平。- 面试视角：常见追问是「能不能做到 $O(1)$ 查询」。答 Alias Method（别名采样）可以在 $O(n)$ 预处理后做到 $O(1)$ 抽样，思路是把所有段重排成 $n$ 个等长的桶、每桶最多两种下标；点到这个名字并说清桶的构造思想即可，通常不要求手写。
易错点总结
- 错误写法：随机落点取
Math.random() * sum后不加 1，即范围为[0, sum-1]，却仍用左开右闭的段划分。用例w = [1, 3]→x = 0时二分找第一个presum[i+1] >= 0，恒为下标 0，下标 0 的概率变成 2/4，正确应为 1/4。- 错误写法：把前缀和累加放进
pickIndex，每次调用重算一遍。用例n = 10000且调用 $10^4$ 次 → 总代价 $10^8$，超时；预处理必须只做一次。- 错误写法：二分右端取
n - 1（前缀和数组的末下标）。用例w = [1, 3]→ 候选包含哨兵之后的非法段号，判定式访问presum[n]越界，或返回等于w.length的非法下标。- 错误写法：判定条件写成
presum[mid] >= x，忘了偏移。用例w = [1, 3]、x = 1→presum[0] = 0 >= 1为假、presum[1] = 1 >= 1为真，收敛到下标 1，正确答案是 0；段i的右端点是presum[i+1]而不是presum[i]。- 错误写法：判定写成严格大于
presum[mid + 1] > x。用例w = [1, 3]、x = 1→ 第 0 段的右端点 1 不满足严格大于，落点被推给下标 1，下标 0 的概率变成 0。- 错误写法：满足条件时写
right = mid - 1。用例w = [1, 3]、x = 1→ 正确答案下标 0 被排除，返回值恒为 1，下标 0 永远抽不到。- 错误写法：不满足条件时写
left = mid。用例w = [1, 3]、x = 4→mid恒等于left，区间不收缩，死循环。- 错误写法：前缀和用
int存但先乘后除做归一化，或按浮点比例比较。用例 权重和达 $10^8$ 且用浮点比较 → 浮点精度误差让边界附近的落点归错段，概率出现肉眼不可见但统计上显著的偏差；整数落点配整数前缀和才是精确的。- 错误写法：直接把下标按权重展开成数组再随机取。用例
w = [100000000]→ 需要 $10^8$ 个元素的数组，内存溢出；正是前缀和要规避的那条路。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 528. 按权重随机选择 | 中等 | 与本题同题，可用来对照前缀和二分与别名采样两种抽样方案 |
| 497. 非重叠矩形中的随机点 | 中等 | 权重变成矩形面积，选中矩形后还要在矩形内做二维均匀抽样 |
| 398. 随机数索引 | 中等 | 目标是在等概率的重复下标中抽样，考察蓄水池而非区间划分 |
| 35. 搜索插入位置 | 简单 | 剥离随机性后剩下的正是同一个左边界二分模板 |
| 34. 在排序数组中查找元素的第一个和最后一个位置 | 中等 | 同样在有序数组上定位区间端点，但要同时求下界与上界 |
| 704. 二分查找 | 简单 | 最基础的有序查找，可用来对照闭区间与左闭右开两套写法 |
| 1011. 在 D 天内送达包裹的能力 | 中等 | 二分的对象从下标换成答案值域，判定条件需要自己构造 |