数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究C++ 中的带黑名单的随机选取
假设我们有一个名为 B 的黑名单。这正在区间 [0, N) 内保留唯一整数，我们必须定义一个函数，以从 NOT in B 的范围 [0, N) 中返回一个均匀的随机整数。我们将通过减少 random() 尝试使这个函数更优化。函数调用。假设输入数组如下
为了解决这个问题，我们将遵循以下步骤 -
定义一个 map
- 我们将使用 N 和数组 v 初始化。
- 对于 initalize i := 0，当 i < v 的 size 时，更新（将 i 增加 1），执行 -
- 如果 v[i] < N，则：，m[v[i]] := -1
- M := N – m 的 size
- n := v 的 size
- 对于 initalize i := 0，当 i < v 的 size 时，更新（将 i 增加 1），执行 -
- 如果 v[i] < M，则 -
- 将 N 减少 1
- 当 N 在 m 中时，执行 -
- 将 N 减少 1
- m[v[i]] := N
- 如果 v[i] < M，则 -
- 定义一个函数 pick()
- x := 随机数模 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
更新于： 2020-06-02
180 次浏览
广告