# 528. Random Pick with Weight

Given an array `w` of positive integers, where `w[i]` describes the weight of index `i`, write a function `pickIndex` which randomly picks an index in proportion to its weight.

Note:

1. `1 <= w.length <= 10000`
2. `1 <= w[i] <= 10^5`
3. `pickIndex` will be called at most `10000` times.

Example 1:

``````Input:
["Solution","pickIndex"]
[[[1]],[]]
Output: [null,0]
``````

Example 2:

``````Input:
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output: [null,0,1,1,1,0]
``````

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. `Solution`‘s constructor has one argument, the array `w``pickIndex` has no arguments. Arguments are always wrapped with a list, even if there aren’t any.

``````class Solution {
public:
Solution(vector<int> w) {
sum = w;
for (int i = 1; i < w.size(); ++i) {
sum[i] = sum[i - 1] + w[i];
}
}

int pickIndex() {
int x = rand() % sum.back(), left = 0, right = sum.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (sum[mid] <= x) left = mid + 1;
else right = mid;
}
return right;
}

private:
vector<int> sum;
};
``````

``````class Solution {
public:
Solution(vector<int> w) {
sum = w;
for (int i = 1; i < w.size(); ++i) {
sum[i] = sum[i - 1] + w[i];
}
}

int pickIndex() {
int x = rand() % sum.back();
return upper_bound(sum.begin(), sum.end(), x) - sum.begin();
}

private:
vector<int> sum;
};
``````

Random Pick Index

Random Point in Non-overlapping Rectangles

https://leetcode.com/problems/random-pick-with-weight/discuss/154024/JAVA-8-lines-TreeMap

https://leetcode.com/problems/random-pick-with-weight/discuss/154772/C%2B%2B-concise-binary-search-solution

https://leetcode.com/problems/random-pick-with-weight/discuss/154044/Java-accumulated-freq-sum-and-binary-search

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation