C++のブラックリストを使用したランダムピック

Bというブラックリストがあるとします。これは範囲[0、N）から一意の整数を保持しているため、範囲[0、N）からBにない均一なランダム整数を返す関数を定義する必要があります。 random（）を減らすことにより、この関数をより最適化します。関数呼び出し。入力配列が次のようであると仮定します

これを解決するには、次の手順に従います-

1つのマップを定義する

• Nと配列vで初期化します。
• iを初期化する場合：=0、i
• if v [i]

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int M;
   map <int,int> m;
   Solution(int N, vector<int>& v) {
      for(int i = 0; i < v.size(); i++){
         if(v[i] < N) m[v[i]] = -1;
      }
      M = N - (int)(m.size());
      int n = v.size();
      for(int i = 0; i < v.size(); i++){
         if(v[i] < M){
            while(m.count(--N));
            m[v[i]] = N;
         }
      }
   }
   int pick() {
      int x = rand() % M;
      return m.count(x)? m[x] : x;
   }
};
main(){
   vector<int> v = {2};
   Solution ob(4,v);
   cout << (ob.pick()) << endl;
   cout << (ob.pick()) << endl;
   cout << (ob.pick()) << endl;
}

入力

Give N = 4 and array [2]

出力

1
1
0