1
class Solution:
2

3
    def __init__(self, nums: List[int]):
4
        # self.nums = nums
5
        # create a hash of values with their list of indices
6
        self.map = defaultdict(list)
7
        for i, v in enumerate(nums):
8
            self.map[v].append(i)
9

10
    def pick(self, target: int) -> int:
11
        return random.sample(self.map[target], 1)[0]
12
        """
13
        reservoir = 0
14
        count = 0
15
        for i in range(len(self.nums)):
16
            if self.nums[i] == target:
17
                count+=1
18
                if random.random() < 1/count:
19
                    reservoir = i
20
        return reservoir
21

22

23
        samp = []
24
        for i in range(len(self.nums)):
25
            if self.nums[i] == target:
26
                samp.append(i)
27
        return (random.sample(samp,1))[0]
28
        """
29

30

31
# Your Solution object will be instantiated and called as such:
32
# obj = Solution(nums)
33
# param_1 = obj.pick(target)