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

题目描述

• insert(val)：当元素 val 不存在时返回 true，并向集合中插入该项，否则返回 false。

• remove(val)：当元素 val 存在时返回 true，并从集合中移除该项，否则返回 false。

• getRandom：随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。

题目解析

思路：

• 数据结构使用链表和哈希表，哈希表用于判断元素val是否已存在，链表用于随机访问

• 而在移除的时候要考虑一个点是链表在移除中间节点时时间复杂度是O(n)，所以需要将要移除的节点移动到链表尾部再来进行移除

代码：