leetcode：528. 按权重随机选择【普通随机失效 + 要用前缀和二分】

分析

前缀和记录每个的权重比
然后二分一个随机数，看看落在哪个区间，就属于哪个数

普通随机

class Solution:

    def __init__(self, w: List[int]):
        self.choices = []
        for i, v in enumerate(w):
            self.choices.extend([i] * v)
        #print(self.choices)

    def pickIndex(self) -> int:
        l, r = 0, len(self.choices) - 1
        while l < r:
            mid = (l + r) // 2
            rr = random.random()
            if rr <= 0.5:
                l = mid + 1
            else:
                r = mid
        
        return self.choices[l]



# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()

使用了多次随机，伪随机数多次混合精度丢失

前缀和二分 只用一次随机

class Solution:

    def __init__(self, w: List[int]):
        self.preSum = list(accumulate(w))
        self.tot = sum(w)


    def pickIndex(self) -> int:
        rr = random.randint(1, self.tot)
        return bisect_left(self.preSum, rr)



# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()

总结

按权重随机选择 = 前缀和 + 二分看看落在哪个区域