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();
*/