LeetCode第 528 题：按权重随机选择(C++)

528. 按权重随机选择 - 力扣（LeetCode）

还是类似蓄水池抽样问题：

LeetCode第 382 题：链表随机节点(C++)_zj-CSDN博客
LeetCode第 398 题：随机数索引(C++)_zj-CSDN博客

这儿需要考虑数组值，也就是权重，权重越大，被选取的概率也就越大。

但是代码一直最后两个用例超时。。。

class Solution {
public:Solution(vector<int>& w) : p(w){}int pickIndex() {//返回值是下标int sum = 0, res = 0;for(int i = 0; i < p.size(); ++i){sum += p[i];if(rand()%sum >= sum-p[i])  res = i;}return res;}
private:vector<int> p;
};

好吧，看了题解之后才发现理解错题意了。这题并不像蓄水池抽样问题，也没有提到数组很大或者数据流之类的字眼。所以前缀和 + 二分就可以：

class Solution {
public:Solution(vector<int>& w) : p(w){for(int i = 1; i < p.size(); ++i)   p[i] += p[i-1];//生成前缀和数组}int pickIndex() {//返回值是下标int i = rand()%p.back() + 1;//1~p.back()的随机数return lower_bound(p.begin(), p.end(), i) - p.begin();}
private:vector<int> p;
};