给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n – 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。
任何在上述范围内且不在黑名单 blacklist 中的整数都应该有同等的可能性被返回。
1. 拒绝采样（超时）
一直生成指定范围内随机数，直到不在黑名单为止
class Solution {
public:
int num;
unordered_set<int> list;
Solution(int n, vector<int>& blacklist) {
num = n;
list = unordered_set<int>(blacklist.begin(),blacklist.end());
}
int pick() {
int x;
while(1){
x = rand()%num;
if(list.count(x)==0) return x;
}
}
};
2. 黑名单映射
class Solution {
public:
unordered_map<int, int> M;//记录左区间黑名单元素，到右区间白名单元素的映射
int t;
Solution(int n, vector<int>& blacklist) {
int m=blacklist.size(), k=n-m;//计算黑名单和白名单长度
t = k;//记录白名单长度，这里左区间白名单，右区间黑名单
unordered_set<int> S;
for(auto& x: blacklist)
if(x >= t)
S.emplace(x);//记录大于等于白名单长度的黑名单元素
//k指针从右区间黑名单第一个位置开始
for(auto& x: blacklist)//处理所有黑名单值
if(x < t){//只用处理在白名单区间的黑名单元素
while(S.count(k))//如果k位置已经存了黑名单值
k++;//指针后移
M[x] = k++;//该值映射到黑名单对应位置，随机到该值不能取，取到黑名单区间的白名单元素
}
}
int pick() {
int x = rand()%t;//取白名单区间随机数
return M.count(x) ? M[x] : x;//如果有映射，说明该值为黑名单元素，取对应映射到
}
};
3. 随机白名单区间
本质上也是做映射，先计算所有白名单区间和白名单各区间前缀和，然后在白名单总长度范围内取随机数，并通过前缀和，判断落在哪一段区间
接着通过映射求取对应区间的随机数，其实就是通过前缀和完成区间的加权随机数，先随机区间，再随机区间内的数
随机白名单区间
class Solution {
private:
default_random_engine e; //随机数种子
uniform_int_distribution<int> dis, dis2;//随机数范围
vector<int>& list;
vector<pair<int, int>> ps; //统计可落的区间
vector<int> lens; //统计每个区间长度，这里方便后面生成白名单范围内随机数，并映射到白名单区间
public:
Solution(int n, vector<int>& blacklist) : list(blacklist){
sort(list.begin(), list.end());//先进行排序方便后面区间划分
//下面的代码便是初始化ps 和 lens
// 处理第一个白名单区间
if(!blacklist.empty()){
if(blacklist[0] + 1 >= 2){//第一个黑名单元素前存在白名单区间
ps.push_back({-1, blacklist[0]});
lens.push_back(blacklist[0]);
}
}
//处理后面的白名单区间
for(int i = 1; i < blacklist.size(); i++){
if(blacklist[i] - blacklist[i - 1] >= 2){//如果黑名单间隔大于等于2，即存在白名单区间
ps.push_back({blacklist[i - 1], blacklist[i]});//加入该白名单区间
lens.push_back(blacklist[i] - blacklist[i - 1] - 1);//加入区间长度（可取点）
}
}
if(blacklist.size() > 0){
if(n - blacklist.back() >= 2){//处理最后一个白名单区间
ps.push_back({blacklist.back(), n});//加入该白名单区间
lens.push_back(n - blacklist.back() - 1);
}
}else{//如果不存在黑名单
ps.push_back({-1, n});//白名单区间为全区间
lens.push_back(n);//长度为n
}
for(int i = 1; i < lens.size(); i++) //前缀和方便计算落点区间
lens[i] += lens[i - 1];
dis = uniform_int_distribution<int>(1, lens.back());//得到白名单长度范围
}
int pick() {
int num = dis(e);//在白名单长度范围内取随机数
int idx = lower_bound(lens.begin(), lens.end(), num) - lens.begin();//二分查找该随机数在哪个区间
dis2 = uniform_int_distribution<int>(ps[idx].first + 1, ps[idx].second - 1);//映射到对应白名单区间并取随机数
int temp = dis2(e);
return temp;
}
};
原创文章，作者：254126420，如若转载，请注明出处：https://blog.ytso.com/270398.html