常数时间，我可以删除/查找数组中的任意元素

这类问题的关键在于，如何结合哈希表和数组，使得数组的删除操作时间复度也变成 O(1)。

01 常数时间插入、删除和获取随机元素

实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

示例：
输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]
解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
提示：
-231 <= val <= 231 - 1
最多调用 insert、remove 和 getRandom 函数 2 * 105 次
在调用 getRandom 方法时，数据结构中 至少存在一个 元素。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

难点在于：

• 插入、删除，获取元素这三个操作的时间复杂度必须是 O(1)；
• getRandom 方法返回的元素必须等概率返回随机元素。

对于 getRandom 方法来说，如果想要等概率和在 O(1) 时间内取出元素，一定要满足：底层用数组实现，且数组必须是紧凑的。

如果使用数组存储元素的话，插入和删除的时间复杂度要为 O(1)，就要在数组尾部进行插入和删除操作。所以，要删除数组中的某一个元素，可以先把这个元素交换到数组的尾部，然后在 pop 掉。

交换两个元素必须通过索引交换，所以需要一个哈希表来记录每个元素值对应的所有。代码如下：

class RandomizedSet {
public:
    // 存储元素的值
    vector<int> nums;
    // 记录每个元素在 nums 中的索引
    unordered_map<int, int> mp;

    RandomizedSet() {
        nums.clear();
        mp.clear();
    }

    bool insert(int val) {
        if (mp.count(val)) {
            return false;
        }
        nums.push_back(val);
        mp[val] = nums.size() - 1;
        return true;
    }

    bool remove(int val) {
        if (!mp.count(val))
            return false;
        int back_val = nums[nums.size() - 1];
        mp[back_val] = mp[val];
        nums[mp[back_val]] = back_val;
        mp.erase(val);
        nums.pop_back();
        return true;
    }

    int getRandom() {
        return nums[rand() % nums.size()];
    }
};

02 避开黑名单的随机数

给定一个整数 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

类似上一题，可以将区间 [0, N) 看作一个数组，然后将 blacklist 中的元素移到数组的最末尾，同时使用一个哈希表进行映射。

根据这个思路，写出第一版代码：

class Solution {
public:
    int sz;
    unordered_map<int, int> mp;
    Solution(int n, vector<int>& blacklist) {
        // 最终数组中的元素
        sz = N - blacklist.size();
        // 最后一个元素的索引
        int last = N - 1;
        // 将黑名单中索引换到最后
        for (int b : blacklist) {
            mp[b] = last;
            last--;
        }
    }
};

如图所示，相当于将黑名单中的数字换到了 [sz, N) 中，同时把 [0, sz) 中黑名单数字映射到了正常数字。

根据这个逻辑，可以写出 pick 函数：

int pick() {
    // 随机选出一个索引
    int index = rand() % sz;
    // 这个索引命中率黑名单，需要被映射到其他位置
    if(mp.count(index)) {
        return mp[index];
    }
    // 若没有命中黑名单，则直接返回
    return index;
}

pick 函数已经没有问题了，但是，构造函数还有两个问题：

第一个问题，如下段代码：

int last = N - 1;
// 将黑名单中的索引换到后面
for (int b : blacklist) {
    mp[b] = last;
    last--;
}

该段代码将黑名单中的 b 映射到了 last，但是不能确定 last 不在 backlist 中。

如下图这种情况，预期应该是 1 映射到 3，但是错误地映射到了 4：

在对 mp[b] 赋值时，要保证 last 一定不在 blacklist 中：

Solution(int N, vector<int>& blacklist) {
    sz = N - blacklist.size();
    // 先将所有黑名单数字放入 mp
    for (int b : blacklist) {
        // 赋值多少都可以，目的是把键存到哈希表中，方便判断数字是否在黑名单中
        mp[b] = 666;
    }
    int last = N - 1;
    for (int b : blacklist) {
        // 跳过所有黑名单中的数字
        while (mp.count(last)) {
            last--;
        }
        // 将黑名单中的索引映射到合法数字
        mp[b] = last;
        last--;
    }
}

第二个问题，如果 blacklist 中的黑名单数字本身就在区间 [sz, N) 中，那么就没有必要在 mp 中建立映射，如图所示：

根本不需要管 4，只需要将 1 映射到 3 上，但是按照 blacklist 的顺序，会把 4 映射到 3。修改代码如下：

Solution(int N, vector<int>& blacklist) {
    sz = N - blacklist.size();
    for (int b : blacklist) {
        mp[b] = 666;
    }
    int last = N - 1;
    for (int b : blacklist) {
        // 如果 b 已经在 [sz, N)
        if (b >= sz) {
            continue;
        }
        while (mp.count(last)) {
            last--;
        }
        mp[b] = last;
        last--;
    }
}