Java实现 LeetCode 528 按权重随机选择（TreeMap）
2024-08-30 10:55:40
528. 按权重随机选择
给定一个正整数数组 w ，其中 w[i] 代表位置 i 的权重，请写一个函数 pickIndex ，它可以随机地获取位置 i，选取位置 i 的概率与 w[i] 成正比。
说明:
1 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex 将被调用不超过 10000 次
示例1:
输入:
[“Solution”,“pickIndex”]
[[[1]],[]]
输出: [null,0]
示例2:
输入:
[“Solution”,“pickIndex”,“pickIndex”,“pickIndex”,“pickIndex”,“pickIndex”]
[[[1,3]],[],[],[],[],[]]
输出: [null,0,1,1,1,0]
输入语法说明：
输入是两个列表：调用成员函数名和调用的参数。Solution 的构造函数有一个参数，即数组 w。pickIndex 没有参数。输入参数是一个列表，即使参数为空，也会输入一个 [] 空列表。
PS：
偷个懒
class Solution {
int sum=0;
private TreeMap<int[], Integer> range = new TreeMap<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
// 区间内
if (o1[0] >= o2[0] && o1[1] < o2[1]) {
return 0;
// 小于，左区间
} else if (o1[1] <= o2[0]) {
return -1;
// 大于
} else {
return 1;
}
}
});
public Solution(int[] w) {
int start;
for(int i=0;i<w.length;i++) {
start = sum;
sum += w[i];
range.put(new int[]{start, sum}, i);
}
}
public int pickIndex() {
int index = (int)(Math.random() * sum);
if (range.get(new int[]{index, index}) == null) {
return 0;
}else{
return range.get(new int[]{index, index});
}
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(w);
* int param_1 = obj.pickIndex();
*/
最新文章
- 分享前端Facebook及Twitter第三方登录
- noj[1581] 筷子
- u盘中放入大于4g单独文件失败解决
- c 函数及指针学习 3
- WPF 绑定五(本身就是数据源)
- Windows+Git+TortoiseGit+COPSSH安装图文教程 转载
- hdu_2665_Kth number(主席树)
- DNS入门
- Java程序设计与数据结构导论--读后感
- 设置PL/SQL 快捷键
- Redhat上为java Maven项目构建基于Jenkins + Github的持续集成环境
- 设置java.library.path的值（Mac/Linux/Windows）
- Java应用开发的一条重要经验：先建立基础设施
- 动态规划：树形DP-景点中心（树的带权重心）
- Java集合类综合
- Scrum Meeting Beta - 4
- 【转】js-ES6学习笔记-Symbol
- 关于JavaScript对象中的一切（一） -- 对象属性
- July 03rd 2017 Week 27th Monday
- 一点一点看JDK源码（五）java.util.ArrayList 后篇之SubList