Leetcode:528. select randomly according to the weight [ordinary random failure + prefix and dichotomy]

analysis

Prefix and record the weight ratio of each
Then divide a random number in half , See which range it falls in , Which number does it belong to

Ordinary random

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()

Used several random , The accuracy of multiple mixing of pseudo-random numbers is lost

Prefix and dichotomy Only one random

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()

summary

Choose randomly by weight = The prefix and + Two points to see which area