labuladong 题解思路 难度困难
给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。
优化你的算法，使它最小化调用语言 内置 随机函数的次数。
实现 Solution 类:
Solution(int n, int[] blacklist)初始化整数n和被加入黑名单blacklist的整数int pick()返回一个范围为[0, n - 1]且不在黑名单blacklist中的随机整数
示例 1：
输入
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
输出
[null, 0, 4, 1, 6, 1, 0, 4]
解释
Solution solution = new Solution(7, [2, 3, 5]);
solution.pick(); // 返回0，任何[0,1,4,6]的整数都可以。注意，对于每一个pick的调用，
// 0、1、4和6的返回概率必须相等(即概率为1/4)。
solution.pick(); // 返回 4
solution.pick(); // 返回 1
solution.pick(); // 返回 6
solution.pick(); // 返回 1
solution.pick(); // 返回 0
solution.pick(); // 返回 4
暴力
class Solution {
public:
vector<int> nums;
Solution(int n, vector<int>& blacklist) {
unordered_set<int> black_set(blacklist.begin(),blacklist.end());
for(int i = 0; i < n;i++) {
if (black_set.find(i)!=black_set.end()) {
continue;
}
nums.emplace_back(i);
}
}
int pick() {
int target = rand()%(nums.size());//生成闭区间[1,total]范围内的一个随机数
return nums[target];
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(n, blacklist);
* int param_1 = obj->pick();
*/
标签：int,黑名单,Solution,710,blacklist,随机数,pick,solution From： https://www.cnblogs.com/zle1992/p/16618312.html