# Random Pick Index

`Reservoir Sampling`

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

**Note:**\
The array size can be very large. Solution that uses too much extra space will not pass the judge.

**Example:**

```
int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);
```

## Analysis

@[lekzeey](https://leetcode.com/lekzeey)

To those who don't understand why it works. Consider the example in the OJ\
\&#xNAN;**{1,2,3,3,3}** with **target 3,**you want to select 2,3,4 with a probability of 1/3 each.

2 : It's probability of selection is 1 \* (1/2) \* (2/3) = 1/3\
3 : It's probability of selection is (1/2) \* (2/3) = 1/3\
4 : It's probability of selection is just 1/3

利用均匀分布的随机数：

```
rand.nextInt(count) < K
```

代表了 k / count的概率新的index `i`会替换已有的sample。

(1 / i) \* (1 - 1/ (i + 1)) \* (1 - 1/(i + 2)) \* ... \* (1 - 1 / n) = 1/n

## Solution

### Reservoir Sampling

121 ms, faster than 94.95%

```java
class Solution {
    private Random rand;
    private int[] nums;
    private int K = 1;

    public Solution(int[] nums) {
        rand = new Random();
        this.nums = nums;
    }

    public int pick(int target) {
        int result = -1;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                count++;
                if (rand.nextInt(count) < K) {
                    result = i;
                }
            }
        }
        return result;
    }
}

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

## Reference

<https://leetcode.com/problems/random-pick-index/discuss/88072/Simple-Reservoir-Sampling-solution>


---

# 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-index.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.