题意：给定一个带权重的数组，平均的返回index
思路：
- 遍历数组，累加数组中的值，并记录在一个sum array中
- 每次从0-totalsum中pick一个值，并用二分查找找到该值在sum array中的位置
- 返回该位置
思想：二分查找
复杂度：时间O（lgn)，空间O(n)
class Solution {
int[] sum;
int total;
Random rand;
public Solution(int[] w) {
sum = new int[w.length];
total = 0;
for(int i=0;i<w.length;i++) {
total += w[i];
sum[i] = total;
}
rand = new Random();
}
public int pickIndex() {
int cur = rand.nextInt(total) + 1;
int s = 0;
int e = sum.length-1;
while(s<e) {
int m = (e-s)/2 + s;
if(cur > sum[m]) {
s = m+1;
} else {
e = m;
}
}
return s;
}
}
