C ++中带权重的随机选择
假设我们有一个由正整数组成的数组w，其中w[i]描述了索引i的权重，我们必须定义一个函数pickIndex()，该函数随机地按其权重选择一个索引。
因此，如果输入类似于[1,3]，则调用pickIndex()五次，则答案可能为−0、1、1、1、0。
为了解决这个问题，我们将遵循以下步骤-
定义数组v
通过初始化程序，初始化为
n：=w[0]
对于范围1到w的i
w[i]：=w[i]+w[i–1]
n：=w[i]
v=w
该pickIndex()会的工作方式如下-
取一个随机数r，对v的最后一个元素执行rmod
从v取最小的数字，不小于r，然后从元素中减去v的第一个数字并返回。
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int n;
vector <int> v;
Solution(vector<int>& w) {
srand(time(NULL));
n = w[0];
for(int i = 1; i < w.size(); i++){
w[i] += w[i - 1];
n = w[i];
}
v = w;
}
int pickIndex() {
return upper_bound(v.begin(), v.end(), rand() % v.back()) - v.begin();
}
};
main(){
vector<int> v = {1,3};
Solution ob(v);
cout << (ob.pickIndex()) << endl;
cout << (ob.pickIndex()) << endl;
cout << (ob.pickIndex()) << endl;
cout << (ob.pickIndex()) << endl;
cout << (ob.pickIndex()) << endl;
}输入项
Initialize with [1, 3] and call pickIndex five times.
输出结果
1 1 1 1 0