Leetcode 398


  Posted on 15 Feb 2017
reservoir sampling


Tutorial


The ith time you see a candidate, you will have a probability of to select it. (i start from 1) So the overall probability of choosing the xth candidate is , 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 . Then we did not change during any encounter with the rest of the candidates. So we need to multiply p by which would finaly result in .

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)