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"]

[[[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 arrayw.pickIndexhas no arguments. Arguments are always wrapped with a list, even if there aren't any.

Analysis

prefix sum + binary search

用accumlated weight sum代表概率分布，每个区间就模拟了均匀分布的概率。比如

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

这样就转化为了search insert index。

这里要找的其实是大于target的最小的数的index。

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

About java.util.Random: https://www.geeksforgeeks.org/java-util-random-nextint-java/

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