528. Random Pick with Weight

#### QUESTION:

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:

``````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.

#### EXPLANATION:

1. 堆w进行求和，同时标记索引位置
2. 随机产生数
3. 将产生的数在索引中找位置（优化点，采用二分查找法
4. 第一个小于这个的，就是对应的位置

#### SOLUTION:

``````class Solution {
Random r;
int[] ints;
int sum;
public Solution(int[] w) {
ints = new int[w.length];
for(int i = 0;i<w.length;i++){
sum+=w[i];
ints[i] = sum;
}
r = new Random(sum);
}

public int pickIndex() {
int random = r.nextInt(sum);
for(int i = 0;i<ints.length;i++){
if(random<ints[i]) return i;
}
return 0;
}
}
``````
>