398. Random Pick Index (Hash Table, Math, Reservoir Sampling, Randomized)

링크 - https://leetcode.com/problems/random-pick-index/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

Hash table에 num값과 그 idx들을 list로 저장해 놓고, 나중에 O(1)으로 pick할 수 있다.

Code

class Solution:

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

    def pick(self, target: int) -> int:
        idxs = self.hash_table[target]
        return random.choice(idxs)
        


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

Complexity

Time Complexity: O(1)

Space Complexity: O(N)