2022-04-21：给定一个包含 [0，n) 中不重复整数的黑名单 blacklist，
写一个函数从 [0, n) 中返回一个不在 blacklist 中的随机整数，
对它进行优化使其尽量少调用系统方法 Math.random()。
1 <= n <= 1000000000，
0 <= blacklist.length < min(100000, N)。
力扣710. 黑名单中的随机数。
答案2022-04-21：
工程题目，黑名单存map。范围是[0,n)，黑马单有m个；那么随机数的范围变成[0,n-m)。然后随机范围内的数字，碰到黑名单的数根据map映射。
代码用rust编写。代码如下：
代码语言：rust复制use rand::Rng;
use std::collections::HashMap;
fn main() {
let solution: Solution = Solution::new(7, vec![2, 3, 5]);
solution.pick();
solution.pick();
solution.pick();
solution.pick();
solution.pick();
solution.pick();
solution.pick();
}
struct Solution {
size: i32,
convert: HashMap<i32, i32>,
}
impl Solution {
fn new(n: i32, blacklist: Vec<i32>) -> Self {
let mut blacklist2: Vec<i32> = vec![];
let mut m: i32 = blacklist.len() as i32;
for i in 0..m {
blacklist2.push(blacklist[i as usize]);
}
let mut blacklist = blacklist2;
blacklist.sort_by(|x, y| x.cmp(&y));
let mut n: i32 = n;
let mut ret = Solution {
size: 0,
convert: HashMap::new(),
};
let mut i: i32 = 0;
while i < m && blacklist[i as usize] < n {
n -= 1;
while n > blacklist[i as usize] {
if n == blacklist[(m - 1) as usize] {
m -= 1;
} else {
ret.convert.insert(blacklist[i as usize], n);
break;
}
n -= 1;
}
i = 1;
}
ret.size = n;
return ret;
}
fn pick(&self) -> i32 {
let ans = rand::thread_rng().gen_range(0, self.size as isize) as i32;
if let Some(x) = self.convert.get(&ans) {
println!("{}", *x);
return *x;
} else {
println!("{}", ans);
return ans;
}
}
}执行结果如下：
在这里插入图片描述左神java代码
