Leetcode 912 Solution

This article provides solution to leetcode question 912 (random-pick-with-weight)
Categories:
Tags:
Access this page by simply typing in "lcs 912" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/random-pick-with-weight

Solution

class Solution:

    def __init__(self, w: List[int]):
        self.a = []
        self.s = 0

        for weight in w:
            self.s += weight
            self.a.append(self.s)

    def pickIndex(self) -> int:
        rand_no = random.randint(1, self.s)

        l = 0
        r = len(self.a) - 1

        while l < r:
            m = (l + r) // 2
            if self.a[m] >= rand_no:
                r = m
            else:
                l = m + 1
        return l


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