通关剑指 Offer——剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

1.题目描述

剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

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

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

示例 :

输入: inputs = ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出: [null, true, false, true, 2, true, false, 2]
解释:
RandomizedSet randomSet = new RandomizedSet();  // 初始化一个空的集合
randomSet.insert(1); // 向集合中插入 1 ， 返回 true 表示 1 被成功地插入

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

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

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

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

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

randomSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.解题思路与代码

2.1 解题思路

题目要求插入删除以及随机读取都是 O(1) 的时间复杂度，那么插入和删除这两步就很容易能够想到使用 HashMap 来操作。但是使用 HashMap 来随机读取的话则不能够满足要求。而我们知道在知道角标的情况下对数组进行读取的时间复杂度是 O(1)，于是我们便可以维护一个数组进行随机读取的操作。由于使用到了 HashMap，便可以指定 HashMap 中的 key 是插入的值， value 是该值在数组中的角标。

在插入操作时，如果 map 中包含 val 的 key ，说明之前已经插入过该 val ，直接 return false；如果没有 val 则执行插入操作，首先拿到插入之后在列表中的索引，然后将 val 和索引放入哈希表中，同时将 val 放入队列。

public boolean insert(int val) {
    if (map.containsKey(val)) {
        return false;
    }
    int index = list.size();
    map.put(val, index);
    list.add(val);
    return true;
}
1
2
3
4
5
6
7
8
9

删除操作稍微麻烦一点，如果 HashMap 中没有要删除的 val 则直接返回 false，如果存在则执行删除流程。首先我们在找到要删除的 val 在数组中的角标 index ，然后将 index 位置设置成当前数组的最后一位元素 last ，同时在 HashMap 中更新 last 在数组中的位置，最后在列表中删除最后一位元素同时将 val 从 map 中移除。以下图为例，当前的 HashMap 和列表情况如第一张图所示，此时要删除数字 3，即 remove(3)，此时先在根据 HashMap 找到 3 在列表中的索引 index 是 1，并且此时列表的最后一个元素是 5，于是我们将列表中 1 位置上的数字设置成 5，同时更新 HashMap 中 5 在列表中的索引，最后在 HashMap 中删除 3 ，同时删除列表中最后一个元素。

随机读取就比较简单了，生成从 0 开始到当前 HashMap 的大小区间内的随机数即 [0, map.size() )，然后从列表中获取该随机数位置上的元素返回即可。代码如下：

public int getRandom() {
    int i = (int) (Math.random() * map.size());
    return list.get(i);
}
1
2
3
4

2.2 代码

class RandomizedSet {
    Map<Integer, Integer> map;
    List<Integer> list;

    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        int index = list.size();
        map.put(val, index);
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        Integer index = map.get(val);
        Integer last = list.get(list.size() - 1);
        list.set(index, last);
        map.put(last, index);
        map.remove(val);
        list.remove(list.size() - 1);
        return true;
    }

    public int getRandom() {
        int i = (int) (Math.random() * map.size());
        return list.get(i);
    }
}
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

2.3 测试结果

通过测试

3.总结

• 使用哈希表和列表来完成，哈希表存放数字及数字在列表中的索引
• 新增和删除时需要同时更新哈希表和列表