Random Pick with Weight

#1

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. `1 <= w.length <= 10000`
2. `1 <= w[i] <= 10^5`
3. `pickIndex` will be called at most `10000` times.

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.

#2

The algorithm below does the following:

• Generate an array with value at index being the total number of elements until that index.
• Generate a random value between `0` and the `total at last index minus one`.
• Do a binary search on the array from step 1 to find the upper bound for the random value, return it. That would be the index with weighted average considered.
``````type Solution struct {
sum []int
}

func Constructor(w []int) Solution {
for i := 1; i < len(w); i++ {
w[i] += w[i - 1]
}

return Solution{w}
}

func (this *Solution) PickIndex() int {
size := len(this.sum)

r := rand.Intn(this.sum[size-1])
s, e := 0, size-1
for s<e{
m := (s+e)/ 2
if this.sum[m]<=r{
s = m+1
} else {
e = m
}
}

return s
}

/**
* Your Solution object will be instantiated and called as such:
* obj := Constructor(w);
* param_1 := obj.PickIndex();
*/
``````

#3

similar logic in Java.

``````class Solution {

int[] weights;
int total;
java.util.Random rand = new java.util.Random();
public Solution(int[] w) {
int sum = 0;
this.weights = new int[w.length];
for(int i=0;i<w.length;i++){
sum += w[i];
weights[i] = sum;
}
System.out.println("total is - "+sum);
this.total = sum;
}

public int pickIndex() {
int val = rand.nextInt(total);
int l=0, r=weights.length-1;
while(l<r){
int m = (l+r)/2;
if(weights[m] > val){
r = m;
}else{
l = m+1;
}
}

return l;
}
}

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