LeetCode 528. 按权重随机选择（Java）

思路：前缀和 + 二分查找

把权重数组 w 展开成"区间"：

w = [1, 3, 2] 前缀和 = [1, 4, 6] 下标 0 占区间 [0, 1) —— 长度 1 下标 1 占区间 [1, 4) —— 长度 3 下标 2 占区间 [4, 6) —— 长度 2

随机生成 r ∈ [0, total)，在前缀和数组中二分查找第一个 > r 的位置 idx，idx 就是答案。
因为每个下标对应的区间长度正好等于它的权重，所以命中概率 = 权重 / 总权重。

代码实现

classSolution{privatefinalint[]prefix;// 前缀和数组privatefinalinttotal;// 总权重privatefinalRandomrandom=newRandom();publicSolution(int[]w){intn=w.length;prefix=newint[n];intsum=0;for(inti=0;i<n;i++){sum+=w[i];prefix[i]=sum;}total=sum;}publicintpickIndex(){// 随机生成 [0, total) 之间的整数inttarget=random.nextInt(total);// 二分查找第一个 prefix[mid] > target 的下标intleft=0,right=prefix.length-1;while(left<right){intmid=left+(right-left)/2;if(prefix[mid]<=target){left=mid+1;}else{right=mid;}}returnleft;}}

示例验证

w = [1, 3, 2]，prefix = [1, 4, 6]，total = 6

随机 r 二分结果 idx 对应区间
0 0 [0, 1)
1 1 [1, 4)
2 1 [1, 4)
3 1 [1, 4)
4 2 [4, 6)
5 2 [4, 6)

命中概率：下标 0 → 1/6，下标 1 → 3/6，下标 2 → 2/6，正好等于权重比例。✅

复杂度

· 构造：O(n)
· pickIndex：O(log n)（二分查找）
· 空间：O(n)（前缀和数组）

易错点

1. 区间是左闭右开：random.nextInt(total) 生成 [0, total)，配合"第一个 > target"的二分，刚好不重不漏。
   若写成 [0, total] 或二分条件写成 >=，边界会出错（target = 0 时容易误判）。
2. 二分边界模板：这里用的是"找第一个满足条件的位置"的经典写法，left < right + right = mid，最后返回 left。
3. 溢出：题目约束下 total ≤ 10^9，int 足够；若权重更大需改用 long。
4. Random 线程安全：java.util.Random 是线程安全的（内部用 CAS），但多线程高并发下可考虑 ThreadLocalRandom.current().nextInt(total) 提升性能：

inttarget=ThreadLocalRandom.current().nextInt(total);

5. 不要每次 pickIndex 重新构建前缀和：前缀和只需构造一次，pickIndex 只做二分。

另一种写法：TreeMap

classSolution{privatefinalTreeMap<Integer,Integer>map=newTreeMap<>();privatefinalinttotal;privatefinalRandomrandom=newRandom();publicSolution(int[]w){intsum=0;for(inti=0;i<w.length;i++){sum+=w[i];map.put(sum,i);// 前缀和 -> 下标}total=sum;}publicintpickIndex(){inttarget=random.nextInt(total);// 返回 key > target 的最小条目returnmap.higherEntry(target).getValue();}}

TreeMap.higherEntry(target) 返回严格大于 target 的最小 key，正好对应二分结果。代码更简洁，但常数略大。

推荐

面试中写前缀和 + 二分最标准，能体现对边界和概率映射的理解。TreeMap 版本可作补充。