398. Random Pick Index

https://leetcode.com/problems/random-pick-index/

Time: O(1)

Space: O(N)

from collections import defaultdict
import random
class Solution:

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

    def pick(self, target: int) -> int:
        n = len(self.d[target])
        randomIndex = random.randint(1,n) - 1
        return self.d[target][randomIndex]
        

另一种解法

Time: O(N)

Space: O(1)

我没想出来这种

def __init__(self, nums):
    self.nums = nums
    
def pick(self, target):
    res = None
    count = 0
    for i, x in enumerate(self.nums):
        if x == target:
            count += 1
            chance = random.randint(1, count)
            if chance == count:
                res = i
    return res