黑名单中的随机数-leetcode710

题目描述

        给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。

优化你的算法，使它最小化调用语言 内置 随机函数的次数。

实现 Solution 类:

• Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数
• int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数

方法一：黑名单映射 

关键点1：等概率随机选择未被列入黑名单的整数——映射策略：将黑名单中的元素映射到白名单中的元素，确保随机数生成范围缩小到[0, bound)

设 blacklist 的长度为 m。所有黑名单数全部在区间 [bound,n) 范围内，可以直接在 [0,bound) 范围内取随机整数。

关键点2：最小化调用内置随机函数的次数——pick()

        将 [0,bound) 范围内的黑名单数，映射到 [bound,n) 范围内的白名单数上。每次 pick() 时，仅生成一次随机数x（范围为[0, bound)），通过哈希表b2w直接查询映射值，时间复杂度为 O (1)，那么：

如果 x 不在黑名单中，则直接返回 x；
如果 x 在黑名单中，则返回 x 映射到 [bound,n) 范围内的白名单数。

在初始化时，构建一个从 [0,bound) 范围内的黑名单数到 [bound,n) 的白名单数的映射：

关键点3：处理黑名单无重复的特性

        将 [bound,n) 范围内的黑名单数存入一个哈希集合 black，使用unordered_set<int>存储后半部分的黑名单元素，利用集合的唯一性和 O (1) 查找特性，快速判断白名单元素是否可用；

初始化白名单数 bonud=n−m；

对于每个 [0,bound) 范围内的黑名单数 b，首先不断增加 w 直至其不在黑名单中，然后将 b 映射到 w 上，并将 w 增加1。

// C++
class Solution {
//哈希表，用于存储黑名单中的数字（键）到白名单中的数字（值）的映射关系。unordered_map<int, int> b2w;int bound;public:Solution(int n, vector<int> &blacklist) {int m = blacklist.size();bound = n - m;unordered_set<int> black;for (int b: blacklist) {if (b >= bound) {black.emplace(b);}}int w = bound;for (int b: blacklist) {if (b < bound) {while (black.count(w)) {++w;}b2w[b] = w++;}}}int pick() {int x = rand() % bound;return b2w.count(x) ? b2w[x] : x;}
};

代码解释

1. unordered_map

unordered_map是C++标准模板库（STL）中的一个关联容器，它存储键值对（key-value pairs）。它与map类似，但它们在内部实现和性能特点上有所不同：

• 内部实现：unordered_map是基于哈希表（hash table）实现的，而map是基于红黑树（一种自平衡二叉搜索树）实现的。

• 性能特点：

  • unordered_map在查找、插入和删除操作上通常具有更快的平均时间复杂度（接近O(1)），但最坏情况下可能会退化到O(n)（例如当大量键产生哈希冲突时）。

  • map的查找、插入和删除操作的时间复杂度都是O(log n)，因为它基于红黑树，操作时间相对稳定。

  unordered_map<int, int>表示这个unordered_map容器的键（key）和值（value）都是int类型。

  b2w是这个unordered_map容器的变量名，可以通过它来访问和操作这个容器，如插入键值对/查找/删除等。

2.vector<int> &blacklist

        一个引用到 vector<int> 类型的对象，blacklist 是一个整数数组，存储了某些“黑名单”数字。

3.unordered_set<int> black

• unordered_set<int>：声明一个 unordered_set 容器，存储 int 类型的元素。

• black：容器变量名，存储后半部分的黑名单数字。

  • unordered_set 是基于哈希表实现的集合容器，存储的元素是唯一的（不允许重复），并且查找、插入和删除操作的平均时间复杂度接近 O(1)。

4.black.count(w)

        unordered_set容器的一个成员函数调用，用于检查集合中是否存在某个元素。如果存在（返回值为 1），说明w不可用，需要继续递增w。如果不存在（返回值为 0）

5.rand() % bound

得到一个范围在[0, bound)内的随机数

时间复杂度分析

分为两个部分：初始化阶段和随机选择阶段

1. 初始化阶段的时间复杂度

步骤 1：处理后半部分的黑名单数字

• 遍历一次黑名单，时间复杂度为 O(m)，其中 m 是黑名单长度。
• unordered_set 的插入操作（emplace）平均时间复杂度为 O(1)。

步骤 2：建立映射关系

• 外层循环遍历黑名单，时间复杂度为 O(m)。
• 内层 while 循环的总次数 最多为 m 次（后半部分的白名单数字至少有 m 个，足够映射前半部分的 m 个黑名单数字）。
• black.count(w) 的时间复杂度为 O(1)。
• 这部分的总时间复杂度为 O(m)。

初始化总时间复杂度：O(m)

2. 随机选择阶段的时间复杂度

• 生成随机数 rand() % bound 的时间复杂度为 O(1)。
• b2w.count(x) 和 b2w[x] 的哈希表查询操作时间复杂度均为 O(1)。

3. 空间复杂度

• unordered_map<int, int> b2w：最多存储 m 个映射关系，空间复杂度为 O(m)。
• unordered_set<int> black：最多存储 m 个元素，空间复杂度为 O(m)。

 执行流程示例

假设：

• n = 10，黑名单为[2, 3, 5, 8]。
• bound = 10 - 4 = 6。
• 后半部分的黑名单数字为[8]（因为 8 >= 6），存入black集合。

映射过程：

1. 处理b=2：
   • 从w=6开始检查。
   • 6不在black中，可用，将2映射到6，然后w递增为7。
2. 处理b=3：
   • 当前w=7，7不在black中，可用，将3映射到7，然后w递增为8。
3. 处理b=5：
   • 当前w=8，8在black中，不可用，w递增为9。
   • 9不在black中，可用，将5映射到9。