原题链接在这里：https://leetcode.com/problems/random-pick-with-weight/
题目：
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.
Note:
1 <= w.length <= 100001 <= w[i] <= 10^5-
pickIndexwill be called at most10000times.
Example 1:
Input:
["Solution","pickIndex"]
[[[1]],[]]
Output: [null,0]
Example 2:
Input:
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output: [null,0,1,1,1,0]
Explanation of Input Syntax:
The input is two lists: the subroutines called and their arguments. Solution's constructor has one argument, the array w. pickIndex has no arguments. Arguments are always wrapped with a list, even if there aren't any.
题解：
The given input array means for current index i, the weight is w[i].
e.g. w = [20, 20, 60]. The weight of choosing 0 is 20, the weight of choosing 1 is 20, the weight of choosing 2 is 60, totally it is 100.
In order to choose by weight, we need to accumlat the total weight, and pick a random number within [1, total weight].
sum = [20, 40, 100]
And binary search where this weight would land.
If sum[mid] == pick, then simply return mid.
Else if sum[mid] < pick, say pick = 50, sum[mid] = 40, then it can't be index 1, since 1 is from 20 to 40. l = mid + 1.
Else if sum[mid] > pick, say pick = 30, sum[mid] = 40, then it could still be index 1, since 1 is from 20 to 40. r = mid.
When using above transion, while loop condision is l < r, it can't be l <= r. Otherwise, it would get out of loop.
Time Complexity: pickIndex, O(logw.length).
Space: O(1). It doesn't have extra array, it is changing input w array.
AC Java:
class Solution {
int [] sum;
Random rand;
public Solution(int[] w) {
for(int i = 1; i<w.length; i++){
w[i] += w[i-1];
}
this.sum = w;
this.rand = new Random();
}
public int pickIndex() {
int len = sum.length;
int n = sum[len-1];
int pick = rand.nextInt(n) + 1;
int l = 0;
int r = len-1;
while(l < r){
int mid = l + (r - l) / 2;
if(sum[mid] == pick){
return mid;
}else if(sum[mid] < pick){
l = mid + 1;
}else{
r = mid;
}
}
return l;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(w);
* int param_1 = obj.pickIndex();
*/