题目
Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.
分析
一个有趣但是很麻烦的做法是，根据给出的点用Numerical methods得出一个可以approximate这些点的函数。变换这个函数使得这个函数在0到1区间的积分为1, 也就是把它变成一个probability density function.
有了pdf之后可以用Inverse transform sampling方法来sample这个pdf
但是我有这么折腾吗?
没有。
另一个简单的方法是
把w里的n个元素想成是n种水果，水果i的数量为w[i]
假如说w是{1,3,2}
那么把w里的3种水果排开就是这样:
苹果 香蕉 香蕉 香蕉 菠萝 菠萝
一共6个水果。这个时候我们要是从1到6这个区间产生一个随机数，就达到了按weight抽取随机数的目标了。但是我们要返回的答案是Index into array w, 所以要再加一层binary search来检索一下我们产生的随机数落入到哪种水果的范围里。
答案
class Solution {
int[] cumsum;
Random rand = new Random();
public Solution(int[] w) {
if(w.length == 0) return;
cumsum = new int[w.length];
cumsum[0] = w[0];
for(int i = 1; i < w.length; i++) {
cumsum[i] = w[i] + cumsum[i - 1];
}
}
public int pickIndex() {
int left = 0, right = cumsum.length;
int target = rand.nextInt(cumsum[cumsum.length - 1]) + 1;
// We want to find the index into cumsum array, such that target falls into
while(left < right) {
int mid = (left + right) / 2;
int mid_val = cumsum[mid];
if(mid_val >= target) {
right = mid;
}
else {
left = mid + 1;
}
}
return left;
}
}
