# Leetcode 398 - Random Pick Index

`Note:`

`Brute force`

- Hash table
- Use more
`extra space`

in exchange of`speed`

.

`Reservoir sampling`

- Based on our prev knowledge, each time we have
`k / N`

possibility to keep current`sample`

. `N`

is the nums who are equal to target we’ve found so far.`k`

is random num between`[1, count]`

.- If
`ran === count`

, which is exactly`1 / N`

possibility, then we keep`current index`

.

- Based on our prev knowledge, each time we have

`Question:`

Given an integer array `nums`

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.

Implement the Solution class:

`Solution(int[] nums)`

Initializes the object with the array`nums`

.`int pick(int target)`

Picks a random index`i`

from`nums`

where`nums[i] == target`

. If there are multiple valid i’s, then each index should have an equal probability of returning.

`Example:`

1 |

`Code:`

`Brute Force:`

1 | /** |

`Reservoir Sampling`

1 | /** |