Random Pick with Weight

给一个数组, 每个数字代表weight, 每个weight是随机选择的权重比例, 求一个方法pickIndex, 返回数组里面weight比例下的随机index.

这个是带权简单随机过程, 高中算法课的数火柴算法. 比如[1,3]最原始的随机过程就是拿四个火柴,1个红色,3个蓝色. 然后随机拿, 换成数组就是求一个随机数, 然后看这个随机数落在哪个区间. 我看答案有logn的解法, 仅仅是优化了pickIndex过程, 算法思想无异.

class Solution {
    int sum = 0;
    Random rand = new Random(); 
    int[] nums;
    public Solution(int[] w) {
        nums = w;
        for(int i : w)
            sum += i;
    }
    
    public int pickIndex() {
        int r = rand.nextInt(sum) + 1; // from 1 to sum+1, 
        for(int i = 0; i < nums.length; i++) {
            r -= nums[i];
            if(r <= 0)
                return i;
        }
        return -1; // err
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(w);
 * int param_1 = obj.pickIndex();
 */