# 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

### 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
// 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)

```java
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](https://www.electricmonk.nl/log/2009/12/23/weighted-random-distribution/)