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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/random/random-pick-with-weight.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.