> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/6.array/380.-insert-delete-getrandom-o-1-m.md).

# 380. Insert Delete GetRandom O(1) (M)

Implement the `RandomizedSet` class:

* `RandomizedSet()` Initializes the `RandomizedSet` object.
* `bool insert(int val)` Inserts an item `val` into the set if not present. Returns `true` if the item was not present, `false` otherwise.
* `bool remove(int val)` Removes an item `val` from the set if present. Returns `true` if the item was present, `false` otherwise.
* `int getRandom()` Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the **same probability** of being returned.

You must implement the functions of the class such that each function works in **average** `O(1)` time complexity.

 

**Example 1:**

```
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.
```

 

**Constraints:**

* `-231 <= val <= 231 - 1`
* At most `2 * 105` calls will be made to `insert`, `remove`, and `getRandom`.
* There will be **at least one** element in the data structure when `getRandom` is called.

### Solution:

就是说就是让我们实现如下一个类：

```cpp
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` 函数？

其实是不能的，因为根据刚才说到的底层实现，元素是被哈希函数「<mark style="color:red;">**分散**</mark>」到整个数组里面的，更别说还有拉链法等等解决哈希冲突的机制，基本做不到 O(1) 时间等概率随机获取元素。

除了 `HashSet`，还有一些类似的数据结构，比如哈希链表 `LinkedHashSet`，我们前文 [手把手实现LRU算法](https://labuladong.github.io/algo/2/20/45/) 和 [手把手实现LFU算法](https://labuladong.github.io/algo/2/20/46/) 讲过这类数据结构的实现原理，本质上就是哈希表配合双链表，元素存储在双链表中。

但是，`LinkedHashSet` 只是给 `HashSet` 增加了有序性，依然无法按要求实现我们的 `getRandom` 函数，因为底层用链表结构存储元素的话，是无法在 O(1) 的时间内访问某一个元素的。

根据上面的分析，对于 `getRandom` 方法，如果想「**等概率**」且「在 O(1) 的时间」取出元素，一定要满足：**底层用数组实现，且数组必须是**<mark style="color:red;">**紧凑**</mark>**的**。

这样我们就可以直接生成随机数作为索引，从数组中取出该随机索引对应的元素，作为随机元素。

**但如果用数组存储元素的话，插入，删除的时间复杂度怎么可能是 O(1) 呢**？

可以做到！对数组尾部进行插入和删除操作不会涉及数据搬移，时间复杂度是 O(1)。

**所以，如果我们想在 O(1) 的时间删除数组中的某一个元素 `val`，可以先把这个元素交换到数组的尾部，然后再 `pop` 掉**。

交换两个元素必须通过索引进行交换对吧，那么我们需要一个哈希表 `valToIndex` 来记录每个元素值对应的索引。

如果仅实现insert/remove的话，那么可以直接用哈希表解决。 使用（动态）数组(`vector` in C++, `list` in Python and `ArrayList` in Java)可以很方便地实现getRandom操作，只要先随机取一个下标，然后返回该下标对应的元素即可。 因此考虑将这两种数据结构结合起来，用一个哈希表和一个数组来维护集合中的元素。

* insert:可以直接在数组后面添加一个新元素，并在哈希表中记录下该元素对应的数组下标。
* remove:先将待删除的元素与数组中最后一个元素调换，由于两个元素的顺序调换了，它们在哈希表中记录的下标也应该调换。调换完成后，待删除元素变成了数组中最后一个元素，故直接将数组长度减一并将该元素从哈希表中移除即可。
* getRandom: 直接随机取一个下标然后返回该下标对应的元素即可。

```cpp
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()];
    }
};


JAVA Version:
public class RandomizedSet {
    
    List<Integer> list;
    Map<Integer, Integer> map;
    Random random;
    public RandomizedSet() {
        // do intialization if necessary
        // 用一个list存数，用一个HashMap记录下<val, index> 数对应的坐标(numToIndex)
        list = new ArrayList<>();
        map = new HashMap<>();
        random = new Random();
    }

    /*
     * @param val: a value to the set
     * @return: true if the set did not already contain the specified element or false
     */
    public boolean insert(int val) {
        if(map.containsKey(val)){
            return false;
        }
        list.add(val);
        map.put(val, list.size()-1);
        return true;
    }

    /*
     * @param val: a value from the set
     * @return: true if the set contained the specified element or false
     */
    public boolean remove(int val) {
        if(!map.containsKey(val)){
            return false;
        }
        int index = map.get(val);
        // list.remove(index); 
        // swap非常神来之笔，可以保证list中其他元素的index order不变，
        // 用map去numToIndex获取的数也是正确的数，
        // 但是map里面已经remove里这个元素的numToIndex，所以不会找到这个元素的
        Collections.swap(list, index, list.size()-1);
        map.put(list.get(index), index);
        map.remove(val);
        list.remove(list.size()-1);
        return true;
    }

    /*
     * @return: Get a random element from the set
     */
    public int getRandom() {
        int r = random.nextInt(list.size());
        // System.out.println(list.get(r));
        return list.get(r);
    }
}
```

注意 `remove(val)` 函数，对 `nums` 进行插入、删除、交换时，都要记得修改哈希表 `valToIndex`，否则会出现错误。

至此，这道题就解决了，每个操作的复杂度都是 O(1)，且随机抽取的元素概率是相等的。