Description
Given an array with possible duplicates, implement a class that returns a random index of the given target number. Each valid index has equal probability.
Examples
Input:
nums = [1,2,3,3,3], target = 3Output:
2, 3, or 4 with equal probabilityExplanation:
Reservoir sampling.
Input:
nums = [1], target = 3Output:
2, 3, or 4 with equal probabilityExplanation:
Edge case with a single-element array.
Input:
nums = [5,7,5,4,3], target = 5Output:
0 or 2 with equal probabilityExplanation:
The target value 5 appears at indices 0 and 2. Since the task requires pick randomly with equal probability, each valid index has a 50% chance of being selected.
Constraints
- •
1 ≤ nums.length ≤ 2 * 10⁴