0528. Random Pick with Weight
https://leetcode.com/problems/random-pick-with-weight
Description
You are given an array of positive integers w
where w[i]
describes the weight of i``th
index (0-indexed).
We need to call the function pickIndex()
which randomly returns an integer in the range [0, w.length - 1]
. pickIndex()
should return the integer proportional to its weight in the w
array. For example, for w = [1, 3]
, the probability of picking the index 0
is 1 / (1 + 3) = 0.25
(i.e 25%) while the probability of picking the index 1
is 3 / (1 + 3) = 0.75
(i.e 75%).
More formally, the probability of picking index i
is w[i] / sum(w)
.
Example 1:
Example 2:
Constraints:
1 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex
will be called at most10000
times.
ac: prefix sum
Last updated