Easiest solution is to use an array to save all the nums[i] == target

```
def __init__(self, nums):
"""
:type nums: List[int]
:type numsSize: int
"""
self.nums = nums
self.ret = []
import random
def pick(self, target):
"""
:type target: int
:rtype: int
"""
i, count, length= 0, 0, len(self.nums)
while i < length:
if self.nums[i] == target:
self.ret.append(i)
count += 1
i += 1
return self.ret[random.randint(0,count-1)]
```

The second solution is to use reservoir sampling

```
def __init__(self, nums):
"""
:type nums: List[int]
:type numsSize: int
"""
self.nums = nums
import random
def pick(self, target):
"""
:type target: int
:rtype: int
"""
i, count, result= 0, 0, -1
while i < len(self.nums):
if self.nums[i] == target:
count += 1
if random.randint(0,count-1) == 0: result = i
i += 1
return result
```

Although solution 2 use less memory than solution 1, it requires more time as multiple calls of randint

Last solution, if you need to run pick function many times from an array with a large size, you need to scan the same array multiple times, that's inefficient. A better way is to use dict to save all the index of nums[i]. Or you can try to sort the nums and do binary search. Here I use dict.

```
def __init__(self, nums):
"""
:type nums: List[int]
:type numsSize: int
"""
self.listnums = collections.defaultdict(list)
for i in range(len(nums)):
self.listnums[nums[i]].append(i)
import random
def pick(self, target):
"""
:type target: int
:rtype: int
"""
index = random.randint(0,len(self.listnums[target])-1)
return self.listnums[target][index]
```

HOWEVER, I got Memory Limit Exceeded error. Not sure why