# \[380]\[中等]\[哈希表] 常数时间插入、删除和获取随机元素

## 题目描述

[380. 常数时间插入、删除和获取随机元素](https://leetcode-cn.com/problems/insert-delete-getrandom-o1/)

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

* insert(val)：当元素 val 不存在时，向集合中插入该项。
* remove(val)：元素 val 存在时，从集合中移除该项。
* getRandom()：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

示例 :

```
// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中，所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();
```

## 解题思路

常数时间插入删除是哈希表所擅长的, 常数时间插入和取随机元素是数组擅长的. 因此思路是将两者综合起来.

数字需要在数组中存储, 才能在随机取数时做到常数时间. 向数组中添加元素也是直接在尾部插入即可. 重点考虑是删除的常数时间实现.

第一点是删除一个数字时, 能快速找到它在数组中的位置. 这个可以用哈希表辅助实现, 哈希表存储每个元素对应的索引位置. 因为重复的元素不会被插入, 所以这个位置索引是唯一的.

第二点是如果这个要删除的数字在数组的中间, 直接删除还要将后面所有的元素前移一位, 时间也不是常数. 但如果要删除的元素在数组的最后一位就没有这个问题. 因此可以在找到要删除的元素位置之后, **交换这个元素和数组最后一个元素, 同时更新哈希表的位置索引**. 然后再删除掉这个元素就没有问题了.

因此使用**哈希表+数组**的数据结构就可以实现题目的要求了.

```python
class RandomizedSet:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.mapping = dict()
        self.array = []

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
        if val not in self.mapping:
            self.mapping[val] = len(self.array)
            self.array.append(val)
            return True
        return False

    def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        if val in self.mapping:
            index = self.mapping[val]
            self.array[index], self.array[-1] = self.array[-1], self.array[index]
            self.mapping[self.array[index]] = index
            self.array.pop()
            del self.mapping[val]
            return True
        return False

    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """
        random_index = random.randint(0, len(self.array) - 1)
        return self.array[random_index]


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
```

## 参考资料

* [常数时间插入、删除和获取随机元素](https://leetcode-cn.com/problems/insert-delete-getrandom-o1/solution/chang-shu-shi-jian-cha-ru-shan-chu-he-huo-qu-sui-j/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/ha-xi-biao/380-chang-shu-shi-jian-cha-ru-shan-chu-he-huo-qu-sui-ji-yuan-su.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.