尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
DeepSeek    LeetCode 528. 按权重随机选择 Java实现
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 版本可作补充。
RELATED

相关推荐

DeepSeek    LeetCode 526. 优美的排列 Java实现

DeepSeek LeetCode 526. 优美的排列 Java实现

LeetCode 526. 优美的排列(Java) 题目要点 用 1 ~ n 构造排列 perm(下标从 1 开始),要求对每个位置 i: perm[i] % i 0 或 i % perm[i] 0返回满足条件的排列数量。方法一:回溯 剪枝 从位置 …

📅 2026/11/6 8:53:48
AI 眼镜 PCBA 代工怎么选:从 BOM 到首件的工艺核查清单

AI 眼镜 PCBA 代工怎么选:从 BOM 到首件的工艺核查清单

一句话结论:AI 眼镜的贴片不是"消费电子代工"的常规活,它更靠近高密度封装工艺。选厂比的不是报价,是工艺窗口和过程数据能不能摊开给你看。#mermaid-svg-YaPSQB8cLY1QmzlT{font-family:"trebuchet ms",verdana,arial,sa…

📅 2026/11/6 8:48:47
基于SpringBoot Vue公司财务管理系统

基于SpringBoot Vue公司财务管理系统

系统介绍: 基于SpringBoot和Vue实现的公司财务管理系统采用前后端分离的架构方式。系统设计了三种角色,分别是管理员、财务人员、员工。 管理员可以在系统后台中进行登录、首页、用户管理、部门与费用科目管理、报销管理、借款管理、记账凭证管理、工资管…

📅 2026/11/6 8:48:47
MORE NEWS

更多资讯

📰

Cline CLI完全指南:在终端运行AI编程代理,实现CI/CD自动化代码审查

人工智能大模型AI Agent代码智能体AI 应用开发工具 【免费下载链接】cline-chinese Cline中文汉化版,Cline是一款在您的 IDE 中运行的自主编程助手,经您许可后可以创建/编辑文件、运行命令、使用浏览器等功能。 项目地址: https://gitcode.co…

📰

Windows域控 设置全域的密码策略 【全域策略生效】

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

📰

Spring+SpringMVC+MyBatis 整合(+拦截器) 详:

SpringSpringMVCMyBatis 整合(拦截器) 详: 目前为止博客基本已将掌握SpringMVC 相关的知识点; 终于来到了最终时刻 SSM 三大框架整合; 搭建SSM 框架的程序架构 SSM 框架整合其实就是:Mybatis Spring SpringMVC 的整合; 前面学习我们知道 &#xff1a…

📰

Oracle数据库基础学习

Oracle数据库基础学习 个人之前就学习过 mysql sqlserver 但笔记没有在CSDN上可能会有些跳跃~ 不明确地方可以看这位大佬的笔记~不是我的. Oracle 简介 OracleDatabase 又名Oracle RDBMS , 是甲骨文公司的一款关系数据库管理系统。(世界上最好的数据库系统;(历史悠…

📰

Java 面试

Java 面试宝典 不定时更新 Java的面试题, 有什么好的 感谢评论告知! 小提示 可以看旁边的文章目录, 自问自带看看自己会不会! 奉上本人Java学习笔记! Java 线程 泛型 集合 SSM Mybatis mybatis中namespace的作用 Namespace是命名空间…

📰

PowerShell监控——监控共享打印机 获取打印记录、打印人员、打印文件等详细信息

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬