# 380. 常数时间插入、删除和获取随机元素
# 题目地址（380. 常数时间插入、删除和获取随机元素）
# 题目描述
设计一个支持在平均 时间复杂度 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();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 前置知识
- 数组
- 哈希表
# 公司
- 阿里
- 腾讯
- 百度
- 字节
# 思路
这是一个设计题。这道题的核心就是考察基本数据结构和算法的操作以及复杂度。
我们来回顾一下基础知识：
- 数组支持随机访问，其按照索引查询的时间复杂度为$O(1)$,按值查询的时间复杂度为$O(N)$， 而插入和删除的时间复杂度为$O(N)$。
- 链表不支持随机访问，其查询的时间复杂度为$O(N)$,但是对于插入和删除的复杂度为$O(1)$（不考虑找到选要处理的节点花费的时间）。
- 对于哈希表，正常情况下其查询复杂度平均为$O(N)$，插入和删除的复杂度为$O(1)$。
由于题目要求 getRandom 返回要随机并且要在$O(1)$复杂度内，那么如果单纯使用链表或者哈希表肯定是不行的。
而又由于对于插入和删除也需要复杂度为$O(1)$，因此单纯使用数组也是不行的，因此考虑多种使用数据结构来实现。
实际上 LeetCode 设计题，几乎没有单纯一个数据结构搞定的，基本都需要多种数据结构结合，这个时候需要你对各种数据结构以及其基本算法的复杂度有着清晰的认知。
对于 getRandom 用数组很简单。对于判断是否已经有了存在的元素，我们使用哈希表也很容易做到。因此我们可以将数组随机访问，以及哈希表$O(1)$按检索值的特性结合起来，即同时使用这两种数据结构。
对于删除和插入，我们需要一些技巧。
对于插入：
- 我们直接往 append，并将其插入哈希表即可。
- 对于删除，我们需要做到 O(1)。删除哈希表很明显可以，但是对于数组，平均时间复杂度为 O(1)。
因此如何应付删除的这种性能开销呢？ 我们知道对于数据删除，我们的时间复杂度来源于
查找到要删除的元素- 以及
重新排列被删除元素后面的元素。
对于 1，我们可以通过哈希表来实现。 key 是插入的数字，value 是数组对应的索引。删除的时候我们根据 key 反查出索引就可以快速找到。
题目说明了不会存在重复元素，所以我们可以这么做。思考一下，如果没有这个限制会怎么样？
对于 2，我们可以通过和数组最后一项进行交换的方式来实现，这样就避免了数据移动。同时数组其他项的索引仍然保持不变，非常好！
相应地，我们插入的时候，需要维护哈希表
图解：
以依次【1，2，3，4】之后为初始状态，那么此时状态是这样的：
而当要插入一个新的5的时候， 我们只需要分别向数组末尾和哈希表中插入这条记录即可。
而删除的时候稍微有一点复杂：
# 关键点解析
- 数组
- 哈希表
- 数组 + 哈希表
- 基本算法时间复杂度分析
# 代码
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()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
复杂度分析
- 时间复杂度：$O(1)$
- 空间复杂度：$O(1)$
# 小然子 - JS题解代码
/**
* Initialize your data structure here.
*/
var RandomizedSet = function() {
this.hash = {}
this.data = []
this.key = 0
};
/**
* Inserts a value to the set. Returns true if the set did not already contain the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.insert = function(val) {
// 如果已经存在，则 return false
if (this.hash[val] !== undefined) {
return false
}
this.hash[val] = this.key // 模拟 hash table 记录
this.data.push(val)
this.key ++
return true
};
/**
* Removes a value from the set. Returns true if the set contained the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.remove = function(val) {
// 如果不存在，则 return false
if (this.hash[val] === undefined) {
return false
}
let i = this.hash[val] // 记录索引值
this.hash[this.data[this.data.length-1]] = i // 将当前最后一位的值对应的索引改为传入值的索引，也可以理解为将数组中的最后一位前置
delete this.hash[val] // 将 val元素 移除
this.data[i] = this.data[this.data.length-1]
this.data.pop() // 将数组中的这个空缺位置用最后一项补位
this.key--
return true
};
/**
* Get a random element from the set.
* @return {number}
*/
RandomizedSet.prototype.getRandom = function() {
return this.data[parseInt(this.key * Math.random())]
};
/**
* Your RandomizedSet object will be instantiated and called as such:
* var obj = new RandomizedSet()
* var param_1 = obj.insert(val)
* var param_2 = obj.remove(val)
* var param_3 = obj.getRandom()
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# remove的思路
感谢漾哥提供的图
← 75. 颜色分类