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. Return the result as an integer.
Examples
Input:
nums = [1,2,3,3,3], target = 3Output:
2Explanation:
Target 3 appears at indices 2,3,4. Reservoir sampling ensures each index has 1/3 probability. Could return 2, 3, or 4.
Input:
nums = [1], target = 3Output:
-1Explanation:
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⁴