关于算法:给我-O1-的时间我可以删除查找数组中的任意元素

读完本文，你不仅学会了算法套路，还能够顺便去 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、对于第二题，数组中含有「空洞」（黑名单数字），也能够利用哈希表奇妙解决映射关系，让数组在逻辑上是紧凑的，不便随机取元素。