LeetCode 528. [Python] Random Pick with Weight
原题链接
中等
作者:
徐辰潇
,
2021-02-09 04:49:53
,
所有人可见
,
阅读 558
class Solution:
#TC: initial: O(len(w)) pickIndex: O(log len(w))
#SC: O(len(w))
#This problem aims to utilize random package to generate weighted random.
#Take this example:
# w = [2,3,4,5,6]
# First take cumSum of w
#cumSum = [2,5,9,14,20]
#Take random pick from seed from [0,19]. Then we have
#seed in [0,2): 0
#seed in [2,5): 1
#seed in [5,9): 2
#seed in [9,14): 3
#seed in [14,20): 4
#For any random seed, use binary research to find the location it should lie in
def __init__(self, w: List[int]):
self.cumSumWeight = [w[0]]
for i in range(1, len(w)):
self.cumSumWeight.append(w[i] + self.cumSumWeight[i-1])
def pickIndex(self) -> int:
seed = random.randint(0, self.cumSumWeight[-1]-1)
if seed < self.cumSumWeight[0]:
return 0
left = 0
right = len(self.cumSumWeight)-1
while(left+1 < right):
mid = left + (right-left) // 2
if self.cumSumWeight[mid] > seed:
right = mid
elif self.cumSumWeight[mid] < seed:
left = mid
else:
return mid+1
return left+1
# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()