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. `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.

Analysis

``````w[] = {2,5,3,4} =>  wsum[] = {2,7,10,14}
``````

then get random val `random.nextInt(14) + 1`, idx is in range `[1,14]`

``````idx in [1,2] return 0
idx in [3,7] return 1
idx in [8,10] return 2
idx in [11,14] return 3
``````

Binary Search的方法见Search Insert Position：https://leetcode.com/problems/search-insert-position/submissions/

java.util.Random.nextInt(int n)

``````Returns a random number.
``````
``````between 0 (inclusive) and n (exclusive).
``````
``````// Java code to demonstrate the working
// of nextInt(n)
import java.util.*;
public class NextInt2 {
public static void main(String args[])
{

// create random object
Random ran = new Random();

// Print next int value
// Returns number between 0-10
int nxt = ran.nextInt(10);

// Printing the random number between 0 and 10
System.out.println("Random number between 0 and 10 is : " + nxt);
}
}
``````

random.nextInt(max) + 1将随机数取值范围从[0, max)变成[1, max];

Time: `O(n)`to init, `O(logn)`for one pick

Space: `O(n)`

Solution

Prefix Sum + Binary Search (Template#1)

``````class Solution {
private int[] accSum;
private int total;
private Random rand;

public Solution(int[] w) {
accSum = new int[w.length];
rand = new Random();

for (int i = 0; i< w.length; i++) {
total += w[i];
accSum[i] = total;
}
}

public int pickIndex() {
int r = rand.nextInt(total) + 1;
int start = 0, end = accSum.length - 1;

while (start <= end) {
int mid = start + (end - start) / 2;
if (accSum[mid] == r) {
return mid;
} else if (accSum[mid] > r) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return start;
}
}

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

Reference

https://leetcode.com/problems/random-pick-with-weight/discuss/154044/Java-accumulated-freq-sum-and-binary-search

http://www.cnblogs.com/grandyang/p/9784690.html

Weighted Random Distribution