读完本文，你不仅学会了算法套路，还能够顺便去 LeetCode 上拿下如下题目：
380.常数工夫插入、删除和获取随机元素
710.黑名单中的随机数
-----------
本文讲两道比拟有技巧性的数据结构设计题，都是和随机读取元素相干的，咱们前文 水塘抽样算法 也写过相似的问题。
这写问题的一个技巧点在于，如何联合哈希表和数组，使得数组的删除操作工夫复杂度也变成 O(1)？
上面来一道道看。
实现随机汇合
这是力扣第 380 题，看下题目：
就是说就是让咱们实现如下一个类：
class RandomizedSet {public: /** 如果 val 不存在汇合中，则插入并返回 true，否则间接返回 false */ bool insert(int val) {} /** 如果 val 在汇合中，则删除并返回 true，否则间接返回 false */ bool remove(int val) {} /** 从汇合中等概率地随机取得一个元素 */ int getRandom() {}}本题的难点在于两点：
1、插入，删除，获取随机元素这三个操作的工夫复杂度必须都是 O(1)。
2、getRandom 办法返回的元素必须等概率返回随机元素，也就是说，如果汇合外面有 n 个元素，每个元素被返回的概率必须是 1/n。
咱们先来剖析一下：对于插入，删除，查找这几个操作，哪种数据结构的工夫复杂度是 O(1)？
HashSet 必定算一个对吧。哈希汇合的底层原理就是一个大数组，咱们把元素通过哈希函数映射到一个索引上；如果用拉链法解决哈希抵触，那么这个索引可能连着一个链表或者红黑树。
那么请问对于这样一个规范的 HashSet，你是否在 O(1) 的工夫内实现 getRandom 函数？
其实是不能的，因为依据方才说到的底层实现，元素是被哈希函数「扩散」到整个数组外面的，更别说还有拉链法等等解决哈希抵触的机制，根本做不到 O(1) 工夫等概率随机获取元素。
除了 HashSet，还有一些相似的数据结构，比方哈希链表 LinkedHashSet，咱们前文 手把手实现LRU算法 和 手把手实现LFU算法 讲过这类数据结构的实现原理，实质上就是哈希表配合双链表，元素存储在双链表中。
然而，LinkedHashSet 只是给 HashSet 减少了有序性，仍然无奈按要求实现咱们的 getRandom 函数，因为底层用链表构造存储元素的话，是无奈在 O(1) 的工夫内拜访某一个元素的。
依据下面的剖析，对于 getRandom 办法，如果想「等概率」且「在 O(1) 的工夫」取出元素，肯定要满足：底层用数组实现，且数组必须是紧凑的。
这样咱们就能够间接生成随机数作为索引，从数组中取出该随机索引对应的元素，作为随机元素。
但如果用数组存储元素的话，插入，删除的工夫复杂度怎么可能是 O(1) 呢？
能够做到！对数组尾部进行插入和删除操作不会波及数据搬移，工夫复杂度是 O(1)。
所以，如果咱们想在 O(1) 的工夫删除数组中的某一个元素 val，能够先把这个元素替换到数组的尾部，而后再 pop 掉。
替换两个元素必须通过索引进行替换对吧，那么咱们须要一个哈希表 valToIndex 来记录每个元素值对应的索引。
有了思路铺垫，咱们间接看代码：
class RandomizedSet {public: // 存储元素的值 vector<int> nums; // 记录每个元素对应在 nums 中的索引 unordered_map<int,int> valToIndex; bool insert(int val) { // 若 val 已存在，不必再插入 if (valToIndex.count(val)) { return false; } // 若 val 不存在，插入到 nums 尾部， // 并记录 val 对应的索引值 valToIndex[val] = nums.size(); nums.push_back(val); return true; } bool remove(int val) { // 若 val 不存在，不必再删除 if (!valToIndex.count(val)) { return false; } // 先拿到 val 的索引 int index = valToIndex[val]; // 将最初一个元素对应的索引批改为 index valToIndex[nums.back()] = index; // 替换 val 和最初一个元素 swap(nums[index], nums.back()); // 在数组中删除元素 val nums.pop_back(); // 删除元素 val 对应的索引 valToIndex.erase(val); return true; } int getRandom() { // 随机获取 nums 中的一个元素 return nums[rand() % nums.size()]; }};留神 remove(val) 函数，对 nums 进行插入、删除、替换时，都要记得批改哈希表 valToIndex，否则会呈现谬误。
至此，这道题就解决了，每个操作的复杂度都是 O(1)，且随机抽取的元素概率是相等的。
避开黑名单的随机数
有了下面一道题的铺垫，咱们来看一道更难一些的题目，力扣第 710 题，我来形容一下题目：
给你输出一个正整数 N，代表左闭右开区间 [0,N)，再给你输出一个数组 blacklist，其中蕴含一些「黑名单数字」，且 blacklist 中的数字都是区间 [0,N) 中的数字。
当初要求你设计如下数据结构：
class Solution {public: // 构造函数，输出参数 Solution(int N, vector<int>& blacklist) {} // 在区间 [0,N) 中等概率随机选取一个元素并返回 // 这个元素不能是 blacklist 中的元素 int pick() {}};pick 函数会被屡次调用，每次调用都要在区间 [0,N) 中「等概率随机」返回一个「不在 blacklist 中」的整数。
这应该不难理解吧，比方给你输出 N = 5, blacklist = [1,3]，那么屡次调用 pick 函数，会等概率随机返回 0, 2, 4 中的某一个数字。
而且题目要求，在 pick 函数中应该尽可能少调用随机数生成函数 rand()。
这句话什么意思呢，比如说咱们可能想出如下拍脑袋的解法：
int pick() { int res = rand() % N; while (res exists in blacklist) { // 从新随机一个后果 res = rand() % N; } return res;}这个函数会屡次调用 rand() 函数，执行效率居然和随机数相干，不是一个丑陋的解法。
聪慧的解法相似上一道题，咱们能够将区间 [0,N) 看做一个数组，而后将 blacklist 中的元素移到数组的最开端，同时用一个哈希表进行映射：
依据这个思路，咱们能够写出第一版代码（还存在几处谬误）：
class Solution {public: int sz; unordered_map<int, int> mapping; Solution(int N, vector<int>& blacklist) { // 最终数组中的元素个数 sz = N - blacklist.size(); // 最初一个元素的索引 int last = N - 1; // 将黑名单中的索引换到最初去 for (int b : blacklist) { mapping[b] = last; last--; } }};如上图，相当于把黑名单中的数字都替换到了区间 [sz, N) 中，同时把 [0, sz) 中的黑名单数字映射到了失常数字。
依据这个逻辑，咱们能够写出 pick 函数：
int pick() { // 随机选取一个索引 int index = rand() % sz; // 这个索引命中了黑名单， // 须要被映射到其余地位 if (mapping.count(index)) { return mapping[index]; } // 若没命中黑名单，则间接返回 return index;}这个 pick 函数曾经没有问题了，然而构造函数还有两个问题。
第一个问题，如下这段代码：
int last = N - 1;// 将黑名单中的索引换到最初去for (int b : blacklist) { mapping[b] = last; last--;}咱们将黑名单中的 b 映射到 last，然而咱们能确定 last 不在 blacklist 中吗？
比方下图这种状况，咱们的预期应该是 1 映射到 3，然而谬误地映射到 4：
在对 mapping[b] 赋值时，要保障 last 肯定不在 blacklist 中，能够如下操作：
// 构造函数Solution(int N, vector<int>& blacklist) { sz = N - blacklist.size(); // 先将所有黑名单数字退出 map for (int b : blacklist) { // 这里赋值多少都能够 // 目标仅仅是把键存进哈希表 // 不便疾速判断数字是否在黑名单内 mapping[b] = 666; } int last = N - 1; for (int b : blacklist) { // 跳过所有黑名单中的数字 while (mapping.count(last)) { last--; } // 将黑名单中的索引映射到非法数字 mapping[b] = last; last--; }}第二个问题，如果 blacklist 中的黑名单数字自身就存在区间 [sz, N) 中，那么就没必要在 mapping 中建设映射，比方这种状况：
咱们基本不必管 4，只心愿把 1 映射到 3，然而依照 blacklist 的程序，会把 4 映射到 3，显然是谬误的。
咱们能够略微批改一下，写出正确的解法代码：
class Solution {public: int sz; unordered_map<int, int> mapping; Solution(int N, vector<int>& blacklist) { sz = N - blacklist.size(); for (int b : blacklist) { mapping[b] = 666; } int last = N - 1; for (int b : blacklist) { // 如果 b 曾经在区间 [sz, N) // 能够间接疏忽 if (b >= sz) { continue; } while (mapping.count(last)) { last--; } mapping[b] = last; last--; } } // 见上文代码实现 int pick() {}};至此，这道题也解决了，总结一下本文的核心思想：
1、如果想高效地，等概率地随机获取元素，就要应用数组作为底层容器。
2、如果要放弃数组元素的紧凑性，能够把待删除元素换到最初，而后 pop 掉开端的元素，这样工夫复杂度就是 O(1) 了。当然，咱们须要额定的哈希表记录值到索引的映射。
3、对于第二题，数组中含有「空洞」（黑名单数字），也能够利用哈希表奇妙解决映射关系，让数组在逻辑上是紧凑的，不便随机取元素。