710. 黑名单中的随机数
给定一个整数 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
提示:
1 <= n <= 1090 <= blacklist.length <= min(105, n - 1)0 <= blacklist[i] < nblacklist 中所有值都 不同pick 最多被调用 2 * 104 次原站题解
java 解法, 执行用时: 45 ms, 内存消耗: 52.8 MB, 提交时间: 2023-01-11 16:48:17
class Solution {
private Map<Integer, Integer> map;
private int bound;
private Random random;
public Solution(int n, int[] blacklist) {
map = new HashMap<>();
bound = n - blacklist.length;
random = new Random();
Set<Integer> set = new HashSet<>();
for(int black: blacklist) {
set.add(black);
}
int i = bound;
for (int black: blacklist) {
if (black < bound) {
while(set.contains(i)) {
i++;
}
map.put(black, i++);
}
}
}
public int pick() {
int r = random.nextInt(bound);
return map.getOrDefault(r, r);
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(n, blacklist);
* int param_1 = obj.pick();
*/
python3 解法, 执行用时: 264 ms, 内存消耗: 26.2 MB, 提交时间: 2023-01-11 16:47:57
class Solution:
def __init__(self, n: int, blacklist: List[int]):
m = len(blacklist)
self.bound = n - m
self.map = dict()
i = self.bound
bset = set(blacklist)
for black in blacklist:
if black < self.bound:
while i in bset:
i += 1
self.map[black] = i
i += 1
def pick(self) -> int:
return self.map.get(r:=randint(0, self.bound - 1), r)
# Your Solution object will be instantiated and called as such:
# obj = Solution(n, blacklist)
# param_1 = obj.pick()
javascript 解法, 执行用时: 192 ms, 内存消耗: 64.9 MB, 提交时间: 2023-01-11 16:46:00
/**
* @param {number} n
* @param {number[]} blacklist
*/
var Solution = function(n, blacklist) {
this.b2w = new Map();
const m = blacklist.length;
this.bound = n - m;
const black = new Set();
for (const b of blacklist) {
if (b >= this.bound) {
black.add(b);
}
}
let w = this.bound;
for (const b of blacklist) {
if (b < this.bound) {
while (black.has(w)) {
++w;
}
this.b2w.set(b, w);
++w;
}
}
};
/**
* @return {number}
*/
Solution.prototype.pick = function() {
const x = Math.floor(Math.random() * this.bound);
return this.b2w.get(x) || x;
};
/**
* Your Solution object will be instantiated and called as such:
* var obj = new Solution(n, blacklist)
* var param_1 = obj.pick()
*/
golang 解法, 执行用时: 100 ms, 内存消耗: 11.6 MB, 提交时间: 2023-01-11 16:45:24
type Solution struct {
b2w map[int]int
bound int
}
func Constructor(n int, blacklist []int) Solution {
m := len(blacklist)
bound := n - m
black := map[int]bool{}
for _, b := range blacklist {
if b >= bound {
black[b] = true
}
}
b2w := make(map[int]int, m-len(black))
w := bound
for _, b := range blacklist {
if b < bound {
for black[w] {
w++
}
b2w[b] = w
w++
}
}
return Solution{b2w, bound}
}
func (s *Solution) Pick() int {
x := rand.Intn(s.bound)
if s.b2w[x] > 0 {
return s.b2w[x]
}
return x
}
/**
* Your Solution object will be instantiated and called as such:
* obj := Constructor(n, blacklist);
* param_1 := obj.Pick();
*/
python3 解法, 执行用时: 288 ms, 内存消耗: 26.1 MB, 提交时间: 2023-01-11 16:44:30
class Solution:
def __init__(self, n: int, blacklist: List[int]):
m = len(blacklist)
self.bound = w = n - m
black = {b for b in blacklist if b >= self.bound}
self.b2w = {}
for b in blacklist:
if b < self.bound:
while w in black:
w += 1
self.b2w[b] = w
w += 1
def pick(self) -> int:
x = randrange(self.bound)
return self.b2w.get(x, x)
# Your Solution object will be instantiated and called as such:
# obj = Solution(n, blacklist)
# param_1 = obj.pick()