problems/380.insert-delete-getrandom-o1.md · limbercode/leetcode-1

## 题目地址（380. 常数时间插入、删除和获取随机元素）

https://leetcode-cn.com/problems/insert-delete-getrandom-o1/description/

## 题目描述

```
设计一个支持在平均 时间复杂度 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();

```

## 思路

这是一个设计题。这道题的核心就是考察基本数据结构和算法的操作以及复杂度。

我们来回顾一下基础知识：

- 数组支持随机访问，其按照索引查询的时间复杂度为$O(1)$,按值查询的时间复杂度为$O(N)$， 而插入和删除的时间复杂度为$O(N)$。
- 链表不支持随机访问，其查询的时间复杂度为$O(N)$,但是对于插入和删除的复杂度为$O(1)$（不考虑找到选要处理的节点花费的时间）。
- 对于哈希表，正常情况下其查询复杂度平均为$O(1)$，插入和删除的复杂度为$O(1)$。

由于题目要求 getRandom 返回要随机，那么如果单纯使用链表以及哈希表肯定是不行的。而又由于对于插入和删除我们也需要平均复杂度为$O(1)$，因此单纯使用数组也是不行的。我们考虑多种使用数据结构来实现。

> 实际上 LeetCode 设计题，几乎没有单纯一个数据结构搞定的，基本都需要多种数据结构结合，这个时候需要你对各种数据结构以及其基本算法的复杂度有着清晰的认知。

对于 getRandom 用数组很简单。对于判断是否已经有了存在的元素，我们使用哈希表也很容易做到。因此我们将数组随机访问，以及哈希表$O(1)$按值检索的特性结合起来，即同时使用这两种数据结构。

对于删除和插入，我们需要一些技巧。

对于插入：

- 我们直接往 append，并将其插入哈希表即可。
- 对于删除，我们需要做到 O(1)。删除哈希表很明显可以，但是对于数组，平均时间复杂度为 O(1)。

因此如何应付删除的这种性能开销呢？ 我们知道对于数据删除，我们的时间复杂度来源于

1. `查找到要删除的元素`
2. 以及`重新排列被删除元素后面的元素`。

对于 1，我们可以通过哈希表来实现。 key 是插入的数字，value 是数组对应的索引。删除的时候我们根据 key 反查出索引就可以快速找到。

对于 2，我们可以通过和数组最后一项进行交换的方式来实现，这样就避免了数据移动。同时数组其他项的索引仍然保持不变，非常好！

> 相应的我们插入的时候，需要维护哈希表

## 关键点解析

- 数组
- 哈希表
- 数组 + 哈希表
- 基本算法时间复杂度分析

## 代码

```python
from random import random

class RandomizedSet:

def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = dict()
        self.arr = []
        self.n = 0

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 in self.data:
            return False
        self.data[val] = self.n
        self.arr.append(val)
        self.n += 1

return True

def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        if val not in self.data:
            return False
        i = self.data[val]
        # 更新data
        self.data[self.arr[-1]] = i
        self.data.pop(val)
        # 更新arr
        self.arr[i] = self.arr[-1]
        # 删除最后一项
        self.arr.pop()
        self.n -= 1

return True

def getRandom(self) -> int:
        """
        Get a random element from the set.
        """

return self.arr[int(random() * self.n)]

# 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()
```

limbercode/leetcode-1

简介

发行版

贡献者

近期动态

limbercode/leetcode-1 .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

limbercode/leetcode-1