黑名单中的随机数

难度:

标签:

题目描述

代码结果

运行时间: 173 ms, 内存: 26.9 MB

// Idea: Use a hashmap to remap the blacklisted values in the range [0, n-1] to values that are not blacklisted.
// This ensures that picking a value from the valid range and remapping it gives us an unbiased result.

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    private Map<Integer, Integer> map;
    private int range;
    private Random random;

    public Solution(int n, int[] blacklist) {
        map = new HashMap<>();
        Set<Integer> blacklistSet = Arrays.stream(blacklist).boxed().collect(Collectors.toSet());
        range = n - blacklist.length;
        int last = n - 1;
        for (int b : blacklist) {
            if (b < range) {
                while (blacklistSet.contains(last)) {
                    last--;
                }
                map.put(b, last);
                last--;
            }
        }
        random = new Random();
    }

    public int pick() {
        int index = random.nextInt(range);
        return map.getOrDefault(index, index);
    }
}

解释

方法:

该题解的思路是将黑名单中小于 n-m 的数映射到 [n-m, n) 的区间内的白名单数，其中 m 为黑名单的长度。这样在随机选取 [0, n-m) 范围内的数时，如果选中的数在黑名单内，就将其映射到对应的白名单数，否则直接返回选中的数。这种做法可以保证在 [0, n-m) 内的数都是等概率被选中的。

时间复杂度:

初始化的时间复杂度为 O(m)，pick 操作的时间复杂度为 O(1)。

空间复杂度:

O(min(n, m))

代码细节讲解

🦆

初始化过程中，你是如何确保从黑名单中正确选择出大于等于`bound`的元素，以建立映射关系的？

▷

在初始化过程中，我首先通过计算 `bound = n - m` 来确定黑名单和非黑名单的分界线。接着，我通过列表推导式 `{b for b in blacklist if b >= self.bound}` 来直接选出所有大于等于 `bound` 的黑名单元素。这个操作确保了只有大于等于 `bound` 的黑名单数被选中并保存在集合 `black` 中，用于后续的映射过程。这样的筛选是直接且有效的，因为它基于集合操作，可以快速完成黑名单元素的分类。

🦆

在构建映射时，你是如何保证每一次寻找白名单数（大于等于`bound`的非黑名单数）时的效率？是否有更优的方式避免每次都从`bound`开始检查？

▷

在当前的构建映射过程中，我使用了 `while w in black` 循环来寻找第一个不在黑名单中的白名单数。这种方法确实可以在每次找到一个小于 `bound` 的黑名单数时，顺序查找第一个可用的白名单数。然而，这个方法在黑名单数接近 `bound` 时可能会变得低效，因为每次都需要从 `bound` 开始检查直到找到一个不在黑名单中的数。一个更优的方法是，使用一个排序好的黑名单数组和一个指针，从 `bound` 开始，如果当前位置的数在黑名单中，则指针向右移动，直到找到不在黑名单中的数，这样可以减少不必要的检查。

🦆

映射关系的构建过程中，为什么选择`while w in black`循环来寻找下一个白名单的值，这种方法会不会因为黑名单密集而导致性能下降？

▷

选择 `while w in black` 循环是为了确保找到的 `w` 值不在黑名单中，以便将黑名单中小于 `bound` 的数映射到这个 `w` 值。确实，这种方法在黑名单数较多且集中在 `bound` 附近时，可能导致性能下降，因为每次寻找非黑名单的 `w` 都可能需要多次循环迭代。为了优化这一点，可以考虑预先计算出所有大于等于 `bound` 的白名单数，然后使用一个更高效的数据结构（如排序数组或哈希表）来快速访问和检查。

相关问题

随机数索引

给你一个可能含有 重复元素 的整数数组 nums ，请你随机输出给定的目标数字 target 的索引。你可以假设给定的数字一定存在于数组中。

实现 Solution 类：

Solution(int[] nums) 用数组 nums 初始化对象。
int pick(int target) 从 nums 中选出一个满足 nums[i] == target 的随机索引 i 。如果存在多个有效的索引，则每个索引的返回概率应当相等。

示例：

输入
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
输出
[null, 4, 0, 2]

解释
Solution solution = new Solution([1, 2, 3, 3, 3]);
solution.pick(3); // 随机返回索引 2, 3 或者 4 之一。每个索引的返回概率应该相等。
solution.pick(1); // 返回 0 。因为只有 nums[0] 等于 1 。
solution.pick(3); // 随机返回索引 2, 3 或者 4 之一。每个索引的返回概率应该相等。

提示：

1 <= nums.length <= 2 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
target 是 nums 中的一个整数
最多调用 pick 函数 10⁴ 次

按权重随机选择

给你一个 下标从 0 开始 的正整数数组 w ，其中 w[i] 代表第 i 个下标的权重。

请你实现一个函数 pickIndex ，它可以 随机地 从范围 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i 的概率为 w[i] / sum(w) 。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

示例 1：

输入：
["Solution","pickIndex"]
[[[1]],[]]
输出：
[null,0]
解释：
Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。

示例 2：

输入：
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
输出：
[null,1,1,1,1,0]
解释：
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4 。

由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
诸若此类。

提示：

1 <= w.length <= 10⁴
1 <= w[i] <= 10⁵
pickIndex 将被调用不超过 10⁴ 次

二叉树中所有距离为 K 的结点获取所有钥匙的最短路径