## Leetcode 398

Posted on 15 Feb 2017
reservoir sampling

### Tutorial

The ith time you see a candidate, you will have a probability of $1/i$ to select it. (i start from 1) So the overall probability of choosing the xth candidate is $1/m$, where m is the total number of candidates. (1 <= x <= m) It is because if we finally decide to choose xth candidate is independent from whether we changed our decision during any encounter with a candidate before the xth. And at the encounter of the xth candidate, we choose to change which is of probability $p=1/x$. Then we did not change during any encounter with the rest of the candidates. So we need to multiply p by $x/(x+1), (x+1)/(x+2), ..., (m-1)/m$ which would finaly result in $1/m$.

### Solution

from random import randint

class Solution(object):

def __init__(self, nums):
"""

:type nums: List[int]
:type numsSize: int
"""
self.nums = nums

def pick(self, target):
"""
:type target: int
:rtype: int
"""
ret = -1
count = 0
for i, x in enumerate(self.nums):
if x == target:
if randint(0, count) == 0:
ret = i
count += 1
return ret

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