力扣 528 按权重随机选择

题意：给定一个带权重的数组，平均的返回index

思路：

1. 遍历数组，累加数组中的值，并记录在一个sum array中
2. 每次从0-totalsum中pick一个值，并用二分查找找到该值在sum array中的位置
3. 返回该位置

思想：二分查找

复杂度：时间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;
    }
}