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 的位置 idxidx 就是答案。因为每个下标对应的区间长度正好等于它的权重所以命中概率 权重 / 总权重。代码实现classSolution{privatefinalint[]prefix;// 前缀和数组privatefinalinttotal;// 总权重privatefinalRandomrandomnewRandom();publicSolution(int[]w){intnw.length;prefixnewint[n];intsum0;for(inti0;in;i){sumw[i];prefix[i]sum;}totalsum;}publicintpickIndex(){// 随机生成 [0, total) 之间的整数inttargetrandom.nextInt(total);// 二分查找第一个 prefix[mid] target 的下标intleft0,rightprefix.length-1;while(leftright){intmidleft(right-left)/2;if(prefix[mid]target){leftmid1;}else{rightmid;}}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)· pickIndexO(log n)二分查找· 空间O(n)前缀和数组易错点区间是左闭右开random.nextInt(total) 生成 [0, total)配合第一个 target的二分刚好不重不漏。若写成 [0, total] 或二分条件写成 边界会出错target 0 时容易误判。二分边界模板这里用的是找第一个满足条件的位置的经典写法left right right mid最后返回 left。溢出题目约束下 total ≤ 10^9int 足够若权重更大需改用 long。Random 线程安全java.util.Random 是线程安全的内部用 CAS但多线程高并发下可考虑 ThreadLocalRandom.current().nextInt(total) 提升性能inttargetThreadLocalRandom.current().nextInt(total);不要每次 pickIndex 重新构建前缀和前缀和只需构造一次pickIndex 只做二分。另一种写法TreeMapclassSolution{privatefinalTreeMapInteger,IntegermapnewTreeMap();privatefinalinttotal;privatefinalRandomrandomnewRandom();publicSolution(int[]w){intsum0;for(inti0;iw.length;i){sumw[i];map.put(sum,i);// 前缀和 - 下标}totalsum;}publicintpickIndex(){inttargetrandom.nextInt(total);// 返回 key target 的最小条目returnmap.higherEntry(target).getValue();}}TreeMap.higherEntry(target) 返回严格大于 target 的最小 key正好对应二分结果。代码更简洁但常数略大。推荐面试中写前缀和 二分最标准能体现对边界和概率映射的理解。TreeMap 版本可作补充。
