398. Random Pick Index

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.

Reservoir Sampling

def __init__(self, nums): 
    self.nums = nums 
     
def pick(self, target): 
    res = None 
    count = 0 
    for i, x in enumerate(self.nums): 
        if x == target: 
            count += 1 
            chance = random.randint(1, count) 
            if chance == count: 
                res = i 
    return res