Random Pick with Weight
给一个数组, 每个数字代表weight, 每个weight是随机选择的权重比例, 求一个方法pickIndex, 返回数组里面weight比例下的随机index.
这个是带权简单随机过程, 高中算法课的数火柴算法. 比如[1,3]最原始的随机过程就是拿四个火柴,1个红色,3个蓝色. 然后随机拿, 换成数组就是求一个随机数, 然后看这个随机数落在哪个区间. 我看答案有logn的解法, 仅仅是优化了pickIndex过程, 算法思想无异.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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(); */ |