Random Pick with Weight

You are given an array weights of positive integers, where weights[i] describes how heavily index i should be favored when picking a random index. Design a structure that repeatedly selects a random index from 0 to weights.length - 1, such that the probability of choosing index i is proportional to weights[i] divided by the sum of all weights.

Implement a class with the following behavior:

• Solution(int[] weights) — initializes the object with the given weight array.
• int pickIndex() — returns a randomly chosen index according to the weighted distribution described above. Each call should be independent of previous calls.

Notes:

• An index with a larger weight must be returned more often, in proportion to its share of the total weight.
• Over a large number of calls, the empirical frequency of each index should approximate weights[i] / sum(weights).
• The returned value must always be a valid index into weights.

Examples

Example 1:

Input:

["Solution", "pickIndex", "pickIndex", "pickIndex"]
[[[3, 1]], [], [], []]

Output:

[null, 0, 1, 0]

Explanation:

weights = [3, 1] means index 0 should be picked about 75% of the time and index 1 about 25% of the time. The exact sequence of outputs shown is just one possible valid run — any sequence is acceptable as long as, across many calls, index 0 comes up roughly three times as often as index 1.

Example 2:

Input:

["Solution", "pickIndex", "pickIndex", "pickIndex", "pickIndex"]
[[[1, 1, 1, 1]], [], [], [], []]

Output:

[null, 2, 0, 3, 1]

Explanation:

All four weights are equal, so each index should be returned with roughly the same frequency (about 25% each) over many calls. The specific sequence shown is only one example of a valid output.

Constraints

• 1 <= weights.length <= 10^4
• 1 <= weights[i] <= 10^5
• pickIndex will be called at most 10^4 times.
• The sum of all weights fits comfortably within a 32-bit integer.