C++での重み付きランダムピック

正の整数の配列wがあり、w [i]がインデックスiの重みを表すとすると、その重みに比例してインデックスをランダムに選択する関数pickIndex（）を定義する必要があります。

したがって、入力が[1,3]のようである場合、pickIndex（）を5回呼び出すと、答えは− 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