给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法,从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。
任何在上述范围内且不在黑名单 blacklist 中的整数都应该有同等的可能性被返回。
一直生成指定范围内随机数,直到不在黑名单为止
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; } } };
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;//如果有映射,说明该值为黑名单元素,取对应映射到 } };
本质上也是做映射,先计算所有白名单区间和白名单各区间前缀和,然后在白名单总长度范围内取随机数,并通过前缀和,判断落在哪一段区间
接着通过映射求取对应区间的随机数,其实就是通过前缀和完成区间的加权随机数,先随机区间,再随机区间内的数
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; } };