刷题记录第五十一天-黑名单中的随机数
2023-12-20 01:30:56
题目描述如下:
给定一个整数n和一个整数黑名单balcklist,目标是写一个随机函数,随机从(0,n-1)中选择一个不属于黑名单里的数,且每个数被取得的概率相同。
思路如下:
- 假设用rand()函数从[ 0,n-balcklist.size() )中随机取一个数,那么取到的数可能是黑名单里的数。
- 假设黑名单里有k个数在[0,size())里,那么就有k个不属于黑名单的数在[size,n-1)里。
- 我们只需要用一个map,将[0,size())中属于黑名单的数一一映射成[size,n-1)中非黑名单数即可。
- 最后,利用rand()%size得到的数如果属于黑名单就返回map映射,否则就返回这个数
class Solution {
public:
int size;
unordered_map<int,int> map;
Solution(int n, vector<int>& blacklist) {
for(int i:blacklist){
map[i]=1;
}
size = n-blacklist.size();
int last = n-1;
for(int num:blacklist){
if(num>=size)
continue;
while(map.count(last)!=0){
last--;
}
map[num]=last;
last--;
}
}
int pick() {
int num=rand()%size;
if(map.count(num)!=0){
return map[num];
}
return num;
}
};
文章来源:https://blog.csdn.net/weixin_45850570/article/details/135095900
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!