380. O(1) 时间插入、删除和获取随机元素
380. O(1) 时间插入、删除和获取随机元素
🟠 🔖 设计
数组
哈希表
数学
随机化
🔗 力扣
LeetCode
题目
Implement the RandomizedSet
class:
RandomizedSet()
Initializes theRandomizedSet
object.bool insert(int val)
Inserts an itemval
into the set if not present. Returnstrue
if the item was not present,false
otherwise.bool remove(int val)
Removes an itemval
from the set if present. Returnstrue
if the item was present,false
otherwise.int getRandom()
Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
You must implement the functions of the class such that each function works in average O(1)
time complexity.
Example 1:
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]
Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.
Constraints:
-2^31 <= val <= 2^31 - 1
- At most
2 * ``105
calls will be made toinsert
,remove
, andgetRandom
. - There will be at least one element in the data structure when
getRandom
is called.
题目大意
实现 RandomizedSet
类:
RandomizedSet()
初始化RandomizedSet
对象bool insert(int val)
当元素val
不存在时,向集合中插入该项,并返回true
;否则,返回false
。bool remove(int val)
当元素val
存在时,从集合中移除该项,并返回true
;否则,返回false
。int getRandom()
随机返回现有集合中的一项(测试用例保证调用此方法时集合中至少存在一个元素)。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数,并满足每个函数的 平均 时间复杂度为 O(1)
。
解题思路
本题的难点在于两点:
- 插入,删除,获取随机元素这三个操作的时间复杂度必须都是
O(1)
。 getRandom
方法返回的元素必须等概率返回随机元素,也就是说,如果集合里面有n
个元素,每个元素被返回的概率必须是1/n
。
HashSet
插入,删除,查找这几种操作的时间复杂度是 O(1)
,但是由于HashSet
存储数据时,是由哈希函数分散地存到整个数组里面的,遇到哈希冲突还会有拉链法等机制,所以做不到 O(1)
时间「等概率」随机获取元素。
如果想「等概率」且「在 O(1)
的时间」取出元素,一定要满足:底层用数组实现,且数组必须是紧凑的。可以直接生成随机数作为索引,从数组中取出该随机索引对应的元素,作为随机元素。
但如果用数组存储元素的话,插入,删除的时间复杂度怎么做到 O(1)
呢?
由于对数组尾部进行插入和删除操作时不会涉及数据搬移,时间复杂度是 O(1)
,所以:
- 插入数据时直接插入到数组尾端即可;
- 删除数组中的某一个元素时,先把这个元素交换到数组的尾部,然后再
pop
掉,交换两个元素时通过索引进行交换,用一个哈希表indexMap
来记录每个元素值对应的索引。
代码
class RandomizedSet {
constructor() {
this.nums = [];
this.map = new Map();
}
// @param {number} val
// @return {boolean}
insert(val) {
if (this.map.has(val)) return false;
this.nums.push(val);
this.map.set(val, this.nums.length - 1);
return true;
}
// @param {number} val
// @return {boolean}
remove(val) {
if (!this.map.has(val)) return false;
const index = this.map.get(val);
const last_val = this.nums[this.nums.length - 1];
this.nums[index] = last_val;
this.nums.pop();
this.map.set(last_val, index);
this.map.delete(val);
return true;
}
// @return {number}
getRandom() {
return this.nums[Math.floor(Math.random() * this.nums.length)];
}
}
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
381 | O(1) 时间插入、删除和获取随机元素 - 允许重复 | 设计 数组 哈希表 2+ |