友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
528. Random Pick with Weight
Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.
Note:
-
1 <= w.length <= 10000 -
1 <= w[i] <= 10^5 -
pickIndexwill be called at most10000times.
Example 1:
Input:
["Solution","pickIndex"]
[[[1]],[]]
Output: [null,0]Example 2:
Input:
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output: [null,0,1,1,1,0]Explanation of Input Syntax:
The input is two lists: the subroutines called and their arguments. Solution’s constructor has one argument, the array `w. pickIndex has no arguments. Arguments are always wrapped with a list, even if there aren’t any.
思路分析
前缀和+二分查找
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-08-16 16:14:41
*/
class Solution {
private int[] preSum;
private Random random;
public Solution(int[] w) {
preSum = new int[w.length + 1];
preSum[0] = 0;
for (int i = 1; i <= w.length; i++) {
preSum[i] = preSum[i - 1] + w[i - 1];
}
random = new Random();
}
public int pickIndex() {
if (preSum.length == 0) return -1;
int target = random.nextInt(preSum[preSum.length - 1]) + 1;
int left = 1, right = preSum.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (preSum[mid] == target) {
right = mid;
} else if (preSum[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1;
}
}