diff options
author | Jack Sangdahl <[email protected]> | 2025-06-23 00:00:56 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-23 00:00:56 -0600 |
commit | 2efadbb88320d468e1ab49f1d954bc09dac239f6 (patch) | |
tree | aa4480451becd9fb26f2440db17dd8d5a7c76b2d /random_pick_weight.py | |
parent | eeb84a6833e37c84f3fc95f533b749a60f894877 (diff) | |
download | leetcode-2efadbb88320d468e1ab49f1d954bc09dac239f6.tar.gz leetcode-2efadbb88320d468e1ab49f1d954bc09dac239f6.zip |
528. random pick with weight
Diffstat (limited to 'random_pick_weight.py')
-rw-r--r-- | random_pick_weight.py | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/random_pick_weight.py b/random_pick_weight.py new file mode 100644 index 0000000..3eda7fd --- /dev/null +++ b/random_pick_weight.py @@ -0,0 +1,36 @@ +# 528. Random Pick with Weight +from itertools import accumulate +from bisect import bisect_left +from random import randint + +""" +you are given a 0-indexed array of positive integers 'w' where 'w[i]' +describes the weight of the i'th index. you need to implement the function +'pickIndex()' which randomly picks an index in the range '[0, w.len - 1]' and +returns it. the probability of picking an index 'i' is 'w[i] / sum(w)'. +""" + + +class Solution(object): + def __init__(self, w): + """ + :type w: List[int] + """ + self.w = list(accumulate(w)) + + def pickIndex(self): + """ + :rtype: int + """ + return bisect_left(self.w, randint(1, self.w[-1])) + + +if __name__ == "__main__": + obj1 = Solution([1]) + obj2 = Solution([1, 3]) + print(obj1.pickIndex()) + print(obj1.pickIndex()) + print(obj1.pickIndex()) + print(obj1.pickIndex()) + print(obj1.pickIndex()) + print(obj1.pickIndex()) |