LeetCode 710. 黑名单中的随机数

2021-09-01 HGNULB 约 10 分钟

文章信息 6 个分类 6 个标签

分类

题目描述

✅ 710. 黑名单中的随机数

题意分析

要什么：给定上界 n 和一份黑名单，设计 pick()，等概率地返回 [0, n) 中任意一个不在黑名单里的整数。构造函数只调用一次，pick 会被调用很多次。
约束透露的信号：n 可以大到 $10^9$，但黑名单长度只有 $10^5$ 级别——白名单可能极其庞大而无法枚举，黑名单却很小。这个悬殊差距决定了：不能把白名单列出来存下，只能用「随机一个小范围的数，再把它映射到某个白名单元素」的思路。pick 高频调用则要求单次是 $O(1)$，把开销全部压在构造函数里。
边界：黑名单中的数保证互不相同且都落在 [0, n) 内；白名单大小 m = n - blacklist.length 保证至少为 1；黑名单元素可能全部集中在前段，也可能全部集中在后段，映射逻辑必须两种极端都成立；「等概率」是硬指标，任何一个白名单元素被选中的概率必须严格相等。

解法：黑名单映射（哈希表）

核心思路

最直接的做法是「拒绝采样」：在 [0, n) 中随机取数，落在黑名单里就重新取。实现极简，但当黑名单占比接近 1（比如 n = 10^5 而黑名单有 10^5 - 1 个数）时，一次成功需要期望约 n / m 轮，pick 的耗时不可控甚至近乎不终止。
另一个方向是把白名单全部列出来后随机取下标，pick 是 $O(1)$，但白名单最大有 $10^9$ 个元素，内存直接爆炸。
突破点在于：我们并不需要白名单的具体内容，只需要一个从 [0, m) 到白名单的双射（m 是白名单大小）。有了双射，随机一个 [0, m) 的下标再映射过去，就能在 $O(1)$ 时间内等概率地取到白名单元素。
怎么构造这个双射？把 [0, n) 切成前段 [0, m) 和后段 [m, n)。前段中大部分数本来就是白名单元素，直接映射到自己；只有前段里那些黑名单元素需要被「重定向」。而重定向的目标从后段里的白名单元素中取——关键的计数恒等式是：前段中黑名单元素的个数，恰好等于后段中白名单元素的个数（因为黑名单总数固定，前段黑名单少一个，后段黑名单就多一个，后段白名单就少一个）。所以两边数量严格匹配，可以一一配对，不多不少。
由此确定要维护的状态：一张哈希表 mp，键是前段中的黑名单元素，值是分配给它的后段白名单元素；同时记录白名单大小 m。不变量是：对任意 x ∈ [0, m)，若 x 在 mp 中则 mp[x] 是一个后段白名单元素、且不同的 x 映射到不同的值；否则 x 自身就是白名单元素。这保证了 [0, m) 的 m 个下标与 m 个白名单元素构成双射，均匀随机下标就等价于均匀随机白名单元素。

解题步骤

计算 m = n - blacklist.length，并把黑名单装进一个哈希集合。为什么需要集合：分配映射目标时要反复判断某个后段的数是不是黑名单元素，集合能 $O(1)$ 回答；用数组线性查会退化。

令指针 cur = m，遍历黑名单中的每个元素 b。为什么 cur 从 m 起：映射目标必须来自后段 [m, n)，从后段的第一个数开始逐个分配。

若 b >= m 就跳过。为什么可以跳过：b 本身位于后段，而随机数只会落在 [0, m)，永远不会取到它，无需为它建立任何映射。

否则先把 cur 向前推进到第一个不在黑名单里的位置，再写入 mp[b] = cur，随后 cur++。为什么要跳过黑名单里的 cur：映射目标必须是白名单元素，否则 pick 会返回黑名单里的数。为什么 cur 只增不减：每个后段白名单元素只能被分配给一个前段黑名单元素，否则两个下标映射到同一个值，双射被破坏、概率也就不再均匀。为什么 cur 永远不会越过 n：由前面的计数恒等式，后段白名单元素的个数恰好等于需要分配的前段黑名单元素个数，资源刚好用完。

pick 里随机取 x ∈ [0, m)，若 x 在 mp 中返回 mp[x]，否则返回 x。为什么这样就等概率：x 在 [0, m) 上均匀分布，而 x 到白名单的对应关系是双射，双射不改变均匀性。

以 n = 6、blacklist = [2, 3] 走一遍。m = 6 - 2 = 4，黑名单集合为 {2, 3}，cur 初始化为 4。处理 b = 2：2 < 4 需要映射；cur = 4 不在黑名单里，于是 mp[2] = 4，cur 推进到 5。处理 b = 3：3 < 4 需要映射；cur = 5 不在黑名单里，于是 mp[3] = 5，cur 推进到 6。构造完成，mp = {2: 4, 3: 5}。此时 pick 会在 {0, 1, 2, 3} 中均匀取 x：取到 0 返回 0，取到 1 返回 1，取到 2 返回 mp[2] = 4，取到 3 返回 mp[3] = 5。四种结果恰好是白名单 {0, 1, 4, 5}，每个概率都是 1/4。再看一个黑名单落在后段的例子 n = 4、blacklist = [3]：m = 3，唯一的黑名单元素 3 满足 b >= m 被跳过，mp 为空，pick 直接在 {0, 1, 2} 中均匀返回，完全正确——这说明「跳过后段黑名单」不是优化而是必要的逻辑分支。

代码实现

// 核心实现：黑名单映射（哈希表），维护必要状态并避免重复处理。
class Solution {
    private final int m;
    private final Map<Integer, Integer> mp = new HashMap<>();
    private final Random rand = new Random();

    public Solution(int n, int[] blacklist) {
        this.m = n - blacklist.length;

        Set<Integer> black = new HashSet<>();
        for (int b : blacklist) {
            black.add(b);
        }

        int cur = m;
        for (int b : blacklist) {
            if (b >= m) {
                continue;
            }
            while (black.contains(cur)) {
                cur++;
            }
            mp.put(b, cur);
            cur++;
        }
    }

    public int pick() {
        int x = rand.nextInt(m);
        return mp.getOrDefault(x, x);
    }
}

// 核心实现：黑名单映射（哈希表），维护必要状态并避免重复处理。
type Solution struct {
    m  int
    mp map[int]int
}

func Constructor(n int, blacklist []int) Solution {
    m := n - len(blacklist)
    black := make(map[int]struct{}, len(blacklist))
    for _, b := range blacklist {
        black[b] = struct{}{}
    }

    mp := make(map[int]int)
    cur := m
    for _, b := range blacklist {
        if b >= m {
            continue
        }
        for {
            if _, ok := black[cur]; !ok {
                break
            }
            cur++
        }
        mp[b] = cur
        cur++
    }

    return Solution{m: m, mp: mp}
}

func (s *Solution) Pick() int {
    x := rand.Intn(s.m)
    if v, ok := s.mp[x]; ok {
        return v
    }
    return x
}

复杂度分析

时间复杂度：构造函数 $O(B)$，B 为黑名单长度；pick 为 $O(1)$。凭什么：构造时黑名单被遍历一次，而内层推进 cur 的循环虽然嵌在外层里，但 cur 全程单调递增且不超过 n，总推进次数被后段长度 B 界住，所以是均摊而非乘积；pick 只做一次随机数生成和一次哈希查找。

空间复杂度：$O(B)$。凭什么：黑名单集合与映射表的元素个数都不超过黑名单长度；与 n 无关，这正是本解法能应对 $n = 10^9$ 的原因。

关键点总结

等概率采样的通用套路是构造双射：把「在一个巨大且带洞的集合上均匀采样」转化为「在一个紧凑的连续区间上均匀采样 + 一个一一映射」。双射不改变均匀性，这是整套方法的理论保证，面试里必须说出来。

前段黑名单数 == 后段白名单数这个计数恒等式是映射能建成的根本原因。遇到「重排 / 补洞 / 配对」类构造，先找这种守恒关系，它往往直接给出算法。

拒绝采样的失效条件要能判断：当被拒绝的比例接近 1 时期望轮数爆炸。看到「黑名单可能占绝大多数」就该主动放弃这条路，并向面试官解释原因，而不是写完再被 hack。

把开销压到构造函数是设计类题的通用取舍：构造只跑一次而查询高频，所以宁可在构造时多花 $O(B)$，也要让 pick 保持 $O(1)$。

面试视角：本题还有一条排序 + 二分的解法——把黑名单排序，随机 x ∈ [0, m) 后二分找出「前面有多少个黑名单元素小于等于当前候选」，据此还原真实值。它的 pick 是 $O(\log B)$，空间同样 $O(B)$，在不想用哈希表或需要有序性时可选。能同时给出两条并比较取舍是加分项。

易错点总结

错误写法：不跳过 b >= m 的黑名单元素，一律建立映射；用例 n = 4、blacklist = [3] → m = 3，为 3 分配映射时 cur 从 3 开始且 3 在黑名单里，cur 一路推进到 4 越界，或映射表里多出永远用不到的键并耗尽后段资源。

错误写法：分配映射目标时不检查 cur 是否在黑名单里；用例 n = 6、blacklist = [2, 4] → m = 4，为 2 分配时直接取 cur = 4，而 4 本身就在黑名单里，pick 有 1/4 概率返回被禁止的 4。

错误写法：cur 在每次分配后不自增；用例 n = 6、blacklist = [0, 1] → m = 4，0 和 1 都被映射到 4，pick 返回 4 的概率变成 1/2、返回 5 的概率变成 0，分布严重失衡。

错误写法：pick 里随机范围写成 [0, n)；用例 n = 6、blacklist = [2, 3] → 取到 4 或 5 时不在 mp 中被原样返回尚可，但取到 2、3 之外的分布已经不均匀，且 4、5 会被重复计入，概率彻底错乱。

错误写法：m 算成 n - 1 或忘记减去黑名单长度；用例 n = 6、blacklist = [2, 3] → 随机范围包含了本应被映射掉的下标之外的值，返回结果可能落在黑名单上。

错误写法：改用拒绝采样「随机到黑名单就重试」；用例 n = 100000、黑名单含 99999 个数 → 单次 pick 期望需要约 $10^5$ 轮随机，实测直接超时。

错误写法：构造函数里把整个白名单枚举出来存进数组；用例 n = 10^9、黑名单只有几个数 → 内存溢出。

错误写法：把映射方向搞反，写成「后段白名单元素 -> 前段黑名单元素」；用例 n = 6、blacklist = [2, 3] → pick 随机出的 2、3 在表中查不到而被原样返回，直接吐出黑名单里的数。

错误写法：用 rand.nextInt(m + 1) 或 rand.Intn(m+1)；用例 n = 6、blacklist = [2, 3] → 可能取到 x = 4，它不在 [0, m) 的定义域内，mp 中查不到从而返回 4，虽然 4 恰好是白名单元素，但它被返回的概率变成了 2/5 而不是 1/4，分布不均。

错误写法：把 cur 的推进循环写成 if 而不是 while；用例 n = 8、blacklist = [0, 4, 5] → m = 5，为 0 分配时 cur = 5 在黑名单里，只跳一次到 6 尚可；但若后段出现连续多个黑名单元素，一次跳跃不足以越过，仍会分配到黑名单上。

相似题目

题目	难度	考察点
380. O(1) 时间插入、删除和获取随机元素	中等	用「数组 + 下标表」维护紧凑集合，删除时靠与末尾交换保持连续，支持动态增删
528. 按权重随机选择	中等	采样不再等概率，靠前缀和 + 二分把非均匀分布转成区间均匀采样
384. 打乱数组	中等	要的是整体排列的均匀性而非单点采样，靠 Fisher-Yates 逐位交换保证