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

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:

Code:

Brute Force:

Reservoir Sampling