刷题记录第五十一天-黑名单中的随机数

本文主要是介绍刷题记录第五十一天-黑名单中的随机数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述如下：
给定一个整数n和一个整数黑名单balcklist，目标是写一个随机函数，随机从(0,n-1)中选择一个不属于黑名单里的数，且每个数被取得的概率相同。
思路如下：

1. 假设用rand()函数从[ 0,n-balcklist.size() )中随机取一个数，那么取到的数可能是黑名单里的数。
2. 假设黑名单里有k个数在[0,size())里，那么就有k个不属于黑名单的数在[size,n-1)里。
3. 我们只需要用一个map，将[0,size())中属于黑名单的数一一映射成[size,n-1)中非黑名单数即可。
4. 最后，利用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;}
};

这篇关于刷题记录第五十一天-黑名单中的随机数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---