aboutsummaryrefslogtreecommitdiff
path: root/random_pick_weight.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-06-23 00:00:56 -0600
committerJack Sangdahl <[email protected]>2025-06-23 00:00:56 -0600
commit2efadbb88320d468e1ab49f1d954bc09dac239f6 (patch)
treeaa4480451becd9fb26f2440db17dd8d5a7c76b2d /random_pick_weight.py
parenteeb84a6833e37c84f3fc95f533b749a60f894877 (diff)
downloadleetcode-2efadbb88320d468e1ab49f1d954bc09dac239f6.tar.gz
leetcode-2efadbb88320d468e1ab49f1d954bc09dac239f6.zip
528. random pick with weight
Diffstat (limited to 'random_pick_weight.py')
-rw-r--r--random_pick_weight.py36
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())