← 返回 meta 的题目列表Weighted Random Picker
类型：online_judge
Given a positive integer array w of length n, where w[i] is the weight of index i, implement a data structure that supports:
init(w): initialize with the weight array.
pickIndex(): return an index i at random with probability w[i] / sum(w).
Requirements:
Each call to pickIndex() should be an independent random trial.
The expected time complexity of pickIndex() should be no worse than O(log n).
Constraints:
1 <= n <= 2 * 10^5
1 <= w[i] <= 10^9
Explain how you handle large prefix sums and random boundary conditions.
Example
Input
w = [1]
call pickIndex() 5 times
Output
总是返回 0