假设我们有一个由正整数组成的数组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的最后一个元素执行r mod
从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