LeetCode 398. [Python] Random Pick Index
原题链接
中等
作者:
徐辰潇
,
2021-02-09 05:07:15
,
所有人可见
,
阅读 430
class Solution:
#TC: init: O(n), pick O(n)
#SC: O(n)
#reservior sampling: conditional probability
def __init__(self, nums: List[int]):
self.nums = nums
def pick(self, target: int) -> int:
res = -1
count = 0
for i in range(len(self.nums)):
if self.nums[i] == target:
count += 1
if count == 1:
res = i
else:
sampling = random.randint(1,count)
if sampling == 1:
res = i
return res
# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.pick(target)