Random Pick with Weight

Given an arraywof positive integers, wherew[i]describes the weight of indexi, write a functionpickIndex 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 most10000times.

Example 1:

Input:

["Solution","pickIndex"]

[[],[]]
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 arrayw.pickIndexhas 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