398.md

398 Random Pick Index

Description

link

---

Solution

• See Code

---

Code

class Solution:

    def __init__(self, nums: List[int]):
        self.nums = collections.defaultdict(list)
        for i, num in enumerate(nums):
            self.nums[num].append(i)
            

    def pick(self, target: int) -> int:
        lst = self.nums[target]
        res = lst[0]
        for i in range(1, len(lst)):
            n = random.random()
            if n < 1 / (1 + i):
                res = lst[i]
        return res


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