O(1)时间插入、删除和获取随机元素

@TBLGSn

2021-08-04

设计一个支持在平均时间复杂度 O(1) 下，执行以下操作的数据结构。

insert(val)：当元素 val 不存在时，向集合中插入该项。插入元素. 平均时间复杂度为 O(1)
remove(val)：元素 val 存在时，从集合中移除该项
getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

思路

遇到问题，我们的第一反应是去搜索我们的大脑，看看是不是我们曾经遇见过类似的情况。经验这个东西总是能够帮助到我们。常见的数据结构包括“数组，栈，链表，队列，树，图,散列表”，我们现在一个一个数据结构的来看:

数组的能在常数时间内在队尾插入一个元素，然而对于删除操作，我们不得不进行查找操作,时间复杂度为O(n)(如果我们维持数组的有序性，那么我们可能在O(lg n) 时间内进行(伪)删除操作)
对于栈来说,插入一个元素的时间复杂度为O(1)，但是如果要删除特定的元素那么时间复杂度可能高达O(n). 对于栈来说，其设定的主要接口只有两种，一个是 push() 压入元素，一种是 pop() 弹出元素
链表分为，单链表和双链表。对于单链表而言，添加一个元素的代价是O(1)。已知元素的前驱节点的情况下，删除一个元素的代价是O(1),如果我们不知道当前元素的位置，我们则需要遍历当前链表，这需要花费O(n). 双链表与单链表大致相似，但我们不需要知道元素的前驱节点.
散列表似乎是最符合题意安排的元素. 它能够在常数时间内完成插入和删除操作，但是它很难满足题目的第三个条件，即在O(1)时间内返回一个随机数。不难想到，要在O(1)时间内返回一个数，那么必须使用
树。无论对于B树，还是红黑树，AVL树，KD树而言，其添加一个元素的时间复杂度都是O(lg n).
图。对于图而言，如果我们要删除一个元素，我们不得不使用“深度优先遍历”或是“广度优先”算法来遍历当前所有的元素。
目前看来 hash表是最符合我们条件的，但是它++++++++++++满足第三个条件是一个大问题. 我们思考一下，是什么阻碍着在常数时间内得到一个随机数。hash 表根据 hash 函数把当前的元素映射到一个表中的一个位置，当出现 hash 冲突时，再通过拉链法等缓解冲突发生的情况.

我们使用一个数组要存储存储当前的所有元素，紧挨着的空间排列，使得我们能够在O(1)时间内完成插入操作. 而对于数组而言，如果我们知道元素的下标，我们也能够在常数的时间内完成删除操作.(这里有一些技巧:与最后一个元素交换位置，再删除最后的那个元素),因此我们再使用一个 hash 表来记录元素当前的位置，就能够在 O(1) 时间内删除一个元素.
对于最棘手的等概率获取随机数,我们则仅仅需要简单的生成一个随机数，最后通过下标随机访问到这个数.

图解

当我们插入元素 57 时，我们在数组的尾部插入它，并在 hash 表中插入 <57,4>（<当前的值val，下标>）

当我们要删除元素 10 时,我们

先根据 hash 表得到，当前元素的下标
与数组最后一个元素进行交换，并更新 hash 表中最后一个元素的下标
维持数据结构的不变性. 删除数组最后一个元素，删除 hash 表中对应的元素.

图源参考2

解答

class RandomizedSet {
public:
    RandomizedSet() {
    }
    
    bool insert(int val) {
        //当前元素 val 已经存在
        if(hash.count(val) != 0) return  false;

        dyarray.push_back(val);
        hash[val] = dyarray.size() - 1;
        return true;
    }
    
    bool remove(int val) {
        //当前元素 不存在
        if(hash.count(val) == 0 ) return false;
        //交换当前元素与最后的元素
        int lastpose = dyarray.size() - 1;
        dyarray[ hash[val]] = dyarray[lastpose];
        //更新下标
        hash[dyarray[lastpose]] = hash[val]; 
        //维持当前数据结构状态(真正的删除)
        dyarray.pop_back(); 
        hash.erase(val); 
        return true; 
    }
    int getRandom() {
        int pose = rand() % dyarray.size();
        return dyarray[pose];
    }
private:
    vector<int> dyarray; //存储元素
    unordered_map<int, int> hash; /*value,下标*/
};

思路

图解

解答

参考