2022-04-21：给定一个包含 [0，n) 中不重复整数的黑名单 blacklist，写一个函数从 [0, n) 中返回一个不在 blacklist 中的随机整数

原创

福大大架构师每日一题

发布于 2022-04-21 20:04:20

1.1K0

发布于 2022-04-21 20:04:20

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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编写。代码如下：

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;
        }
    }
}

执行结果如下：