在C ++中随机选择黑名单

假设我们有一个称为B的黑名单。这是在[0，N）范围内寻找唯一整数，我们必须定义一个函数，以返回范围[0，N）范围内的统一随机整数，该整数不在B中。我们将尝试通过减少使该功能更加优化random()。函数调用。假设输入数组像

为了解决这个问题，我们将遵循以下步骤-

定义一张映射

• 我们将使用N和数组v进行初始化。

• 对于initalize i：= 0，当i <v的大小时，更新（将i增加1），执行-

• 如果v [i] <N，则：，m [v [i]]：= -1

• M：= N – m的大小

• n：= v的大小

• 对于初始化i：= 0，当i <v的大小时，更新（将i增加1），执行-

• 将N减少1

• 当N在m中时，执行-

• m [v [i]]：= N

• 将N减少1

• 如果v [i] <M，则-

• 定义功能 pick()

• x：=随机数mod M

• 返回（如果x在m中存在，则m [x]，否则x）

让我们看下面的实现以更好地理解-

示例

#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