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的最后一个元素执行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