LeetCode_随机化_困难_710.黑名单中的随机数

朴灿烈づ我的快乐病毒、 2023-10-06 22:23 14阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个整数 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 <= 109  
0 <= blacklist.length <- min(105, n - 1)  
0 <= blacklist\[i\] < n  
blacklist 中所有值都 不同  
pick 最多被调用 2 \* 104 次

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/random-pick-with-blacklist

## 2.思路 ##

（1）白名单  
一个比较容易想到的方法就是先将 0 ~ n - 1 这些数存储到 set 集合中，然后再根据黑名单 blacklist，去除 set 中相关的数，最后再将 set 中剩余的数添加到 nums 中，整个过程就相当于在维护白名单 nums，保证向里面存储的数全部都是可以正常获取的。但是由于 n 的值可以非常大，所以在 LeetCode 上运行时会出现“超出内存限制”的提示！

（2）随机化  
本思路需要现有[LeetCode\_随机化\_中等\_380. O(1) 时间插入、删除和获取随机元素][LeetCode_380. O_1_]这题做铺垫。思路参考[常数时间删除/查找数组中的任意元素][Link 1]

## 3.代码实现（Java） ##

//思路1————白名单（在LeetCode中会超出内存限制）
    class Solution {
        
        
        //使用数组作为底层容器
        List<Integer> nums;
        //创建随机化对象
        Random random;
    
        public Solution(int n, int[] blacklist) {
        
            //初始化对象
            nums = new ArrayList<>();
            random = new Random();
            Set<Integer> hashSet = new HashSet<>();
            //向hashSet中存储0 ~ n - 1之间的所有整数
            for (int i = 0; i < n; i++) {
        
                hashSet.add(i);
            }
            //根据黑名单blacklist，去除hashSet中相关的数
            for (int bn : blacklist) {
        
                hashSet.remove(bn);
            }
            //将hashSet中剩余的数添加到nums中（维护白名单）
            for (int rn : hashSet) {
        
                nums.add(rn);
            }
        }
        
        public int pick() {
        
            //random.nextInt(nums.size()):随机生成一个[0~nums.size()-1]之间的任意整数
            int randomIndex = random.nextInt(nums.size());
            return nums.get(randomIndex);
        }
    }
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(n, blacklist);
     * int param_1 = obj.pick();
     */

//思路2————随机化
    class Solution {
        
        
        //记录[0, n - 1]范围内不在黑名单中的整数的个数
        int size;
        HashMap<Integer, Integer> map = new HashMap<>();
        Random random;
    
        public Solution(int n, int[] blacklist) {
        
            random = new Random();
            size = n - blacklist.length;
            //将黑名单中的所有整数存储到map中，键值对中的键为整数，值可以是其它任何数
            for (int bn : blacklist) {
        
                map.put(bn, 1);
            }
            int last = n - 1;
            //把黑名单中的整数都交换到区间[size, n)中，同时把[0, size)中的黑名单数字映射到正常数字
            for (int bn : blacklist) {
        
                //如果 bn 在区间[size, n)内，可以直接忽略
                if (bn >= size) {
        
                    continue;
                }
                while (map.containsKey(last)) {
        
                    last--;
                }
                map.put(bn, last);
                last--;
            }
        }
        
        public int pick() {
        
            //随机选取一个索引
            int randomIndex = random.nextInt(size);
            if (map.containsKey(randomIndex)) {
        
                return map.get(randomIndex);
            } else {
        
                return randomIndex;
            }
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(n, blacklist);
     * int param_1 = obj.pick();
     */

[LeetCode_380. O_1_]: https://blog.csdn.net/weixin_43004044/article/details/124158901
[Link 1]: https://labuladong.gitee.io/algo/2/18/30/