在C ++中随机选择黑名单
假设我们有一个称为B的黑名单。这是在[0，N）范围内寻找唯一整数，我们必须定义一个函数，以返回范围[0，N）范围内的统一随机整数，该整数不在B中。我们将尝试通过减少使该功能更加优化random()。函数调用。假设输入数组像
为了解决这个问题，我们将遵循以下步骤-
定义一张映射
我们将使用N和数组v进行初始化。
对于initalizei：=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：=随机数modM
返回（如果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