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
- pickIndex will be called at most 10000 times.
Example 1:
1
2
3
4
| Input:
["Solution","pickIndex"]
[[[1]],[]]
Output: [null,0]
|
Example 2:
1
2
3
4
| 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.
Solution:
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
| class Solution {
private int[] cum;
private int sum = 0;
public Solution(int[] w) {
cum = new int[w.length];
for (int i = 0; i < w.length; i++) {
sum += w[i];
cum[i] = sum;
}
System.out.println(Arrays.toString(cum));
}
public int pickIndex() {
int idx = (int) (Math.random() * sum) + 1;
int l = 0;
int r = cum.length - 1;
System.out.println(idx);
while (l < r) {
int m = l + (r - l) / 2;
if (idx > cum[m]) {
l = m + 1;
} else {
r = m;
}
}
return l;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(w);
* int param_1 = obj.pickIndex();
*/
|