题目链接

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

题目描述

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

提示：

• −231<=val<=231−1-2^{31} <= val <= 2^{31} - 1−231<=val<=231−1
• 最多进行 2∗1052 * 10^52∗105 次 insert， remove和 getRandom方法调用
• 当调用 getRandom方法时，集合中至少有一个元素

解法：哈希表 + 随机化

对于一个元素我们可以用一个哈希表 m来记录，这样我们就能实现 O(1)O(1)O(1)的 insert和 remove。

对于题目要求的返回随机元素，且概率相同。我们可以用一个列表 nums存储插入的元素（每次插入都插入到末尾，删除也从末尾删除），这样也是 O(1)O(1)O(1)。

m插入的 key是插入元素的值，value是该元素在 nums中的下标。

insert操作：

remove操作：

getRandom操作：直接返回随机下标 randomIdx = rand() % nums.size()的元素 nums[randomIdx]即可。

时间复杂度： O(n)O(n)O(n)

C++代码：

const int N = 2e5+10;class RandomizedSet {
public:int a[N];int idx = -1;unordered_map m;/** Initialize your data structure here. */RandomizedSet() {srand((unsigned)time(nullptr));}/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */bool insert(int val) {//已经存在了 返回falseif(m.count(val)) return false;a[++idx] = val;m[val] = idx;return true;}/** Removes a value from the set. Returns true if the set contained the specified element. */bool remove(int val) {//如果不存在 返回 falseif(!m.count(val)) return false;int pos = m[val];a[pos] = a[idx];if(pos != idx) m[a[pos]] = pos;idx--;m.erase(val);return true;}/** Get a random element from the set. */int getRandom() {int randomIdx = rand() % (idx + 1);return a[randomIdx];}
};/*** Your RandomizedSet object will be instantiated and called as such:* RandomizedSet* obj = new RandomizedSet();* bool param_1 = obj->insert(val);* bool param_2 = obj->remove(val);* int param_3 = obj->getRandom();*/

Python代码：

class RandomizedSet:def __init__(self):"""Initialize your data structure here."""self.nums = []self.m = {}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.m:return Falsen = len(self.nums)self.m[val] = nself.nums.append(val)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.m:return Falsepos = self.m[val]self.nums[pos] = self.nums[-1]self.m[self.nums[pos]] = posself.nums.pop()del self.m[val]return True        def getRandom(self) -> int:"""Get a random element from the set."""return choice(self.nums)# 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()