O(1) 时间插入、删除和获取随机元素（腾讯）
解题思路：
-
对于 insert 和 remove 操作容易想到使用「哈希表」来实现 O(1) 复杂度，对于 getRandom 操作，比较理想的情况是能够在一个数组内随机下标进行返回；
-
insert 操作：使用哈希表判断 val 是否存在，存在的话返回 false，否则将其添加到 nums，更新 idx，同时更新哈希表；
-
remove 操作：使用哈希表判断 val 是否存在，不存在的话返回 false，否则从哈希表中将 val 删除，同时取出其所在 nums 的下标 inx，然后将 nums[nums.length-1] 赋值到 inx 位置，然后删除 nums[nums.length-1] 元素；
-
getRandom 操作：人为确保了 [0, idx] 均为存活值，因此直接在 [0, idx + 1)范围内进行随机即可；
复杂度：
-
时间复杂度：所有操作均为 O(1)；
-
空间复杂度：O(n)；
代码实现：
TS
JS
class RandomizedSet {
list: Array<number>;
map: object;
constructor() {
this.list = [];
this.map = {};
}
insert(val: number): boolean {
if (val in this.map) {
return false;
}
this.list.push(val);
this.map[val] = this.list.length - 1; // ->索引
return true;
}
remove(val: number): boolean {
if (val in this.map) {
// 找到要删除的元素的索引
const index = this.map[val];
let last = this.list[this.list.length - 1];
// 将尾部元素放到 要删除的元素的位置
this.list[index] = last;
this.map[last] = index;
// 删掉尾元素
delete this.map[val];
this.list.pop();
return true;
}
return false;
}
getRandom(): number {
const i = Math.floor(Math.random() * this.list.length);
return this.list[i];
}
}
var RandomizedSet = function () {
this.list = []
this.map = {}
};
RandomizedSet.prototype.insert = function (val) {
if (val in this.map) {
return false
}
this.list.push(val)
this.map[val] = this.list.length - 1 // ->索引
return true
};
RandomizedSet.prototype.remove = function (val) {
if (val in this.map) {
const index = this.map[val]
let last = this.list[this.list.length - 1]
this.list[index] = last
this.map[last] = index
// [1,4,3]
delete this.map[val]
this.list.pop()
return true
} else {
return false
}
};
RandomizedSet.prototype.getRandom = function () {
const i = Math.floor(Math.random() * this.list.length)
return this.list[i]
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
341.扁平化嵌套列表迭代器
上一篇
评论
