leetcode380：常数时间插入、删除和获取随机元素 #48
Comments
let RandomizedSet = function() {
this.list = []
this.map = {}
};
RandomizedSet.prototype.insert = function(val) {
if(this.map[val]) return false
this.list.push(val)
this.map[val] = this.list.length
return true
};
RandomizedSet.prototype.remove = function(val) {
if(!this.map[val]) return false
const final = this.list[this.list.length-1]
// 下面这块主要是把要数组的尾值赋给对应的val值的位置，之后把数组最后的值踢出去即可
const index = this.map[val]
// 这里的index-1即我们拿到的index不是数组的下标，还需要减1。
this.list[index-1] = final
this.map[final] = index
delete this.map[val]
this.list.pop()
return true
};
RandomizedSet.prototype.getRandom = function() {
const index = Math.floor(Math.random() * this.list.length)
return this.list[index]
}; |
这个getRandom不是要概率相等吗 这个概率为什么是相等的 |
/**
* Initialize your data structure here.
*/
var RandomizedSet = function() {
this.list = [];
this.map = {};
};
/**
* Inserts a value to the set. Returns true if the set did not already contain the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.insert = function(val) {
if(!this.map[val]){
this.list.push(val)
this.map[val] = this.list.length
return true
}else{
return false
}
};
/**
* Removes a value from the set. Returns true if the set contained the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.remove = function(val) {
if(this.map[val]){
this.list = this.list.filter(item => item != val)
delete this.map[val]
return true
}else{
return false
}
};
/**
* Get a random element from the set.
* @return {number}
*/
RandomizedSet.prototype.getRandom = function() {
function randomFrom(lowerValue,upperValue){
return Math.floor(Math.random() * (upperValue - lowerValue) + lowerValue);
}
return this.list[randomFrom(0, this.list.length)]
};
/**
* Your RandomizedSet object will be instantiated and called as such:
* var obj = new RandomizedSet()
* var param_1 = obj.insert(val)
* var param_2 = obj.remove(val)
* var param_3 = obj.getRandom()
*/ |
|
自己没想出来，看了题解的提示想到用Map和数组结合的方式。不得不说remove的操作因为惯性思维不太容易想到 /**
* Initialize your data structure here.
*/
var RandomizedSet = function () {
//表示数组中的对应的值的下标是多少
//然后删除的时候就可以根据val找到数组里面的下标 然后在数组中进行删除
this.map = new Map();
//存放值
this.values = [];
};
/**
* Inserts a value to the set. Returns true if the set did not already contain the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.insert = function (val) {
//如果已经有这个值了就返回false
if (this.map.has(val)) {
return false;
} else {
//在表中记录插入的值在数组中的下标
this.map.set(val, this.values.length);
//在数组中添加这个值
this.values.push(val);
return true;
}
};
/**
* Removes a value from the set. Returns true if the set contained the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.remove = function (val) {
if (this.map.has(val)) {
// 找到要删除的值的下标
const deleteIndex = this.map.get(val);
// 得到最后一个元素
const lastVal = this.values.pop();
// 用最后一个数代替要删除的值
this.values[deleteIndex] = lastVal;
// 更新本来是最后一个元素在map中记录的下标
this.map.set(lastVal, deleteIndex);
// 在map中删除
this.map.delete(val);
return true;
} else {
//如果没有这个值就返回false
return false;
}
};
/**
* Get a random element from the set.
* @return {number}
*/
RandomizedSet.prototype.getRandom = function () {
let size = this.values.length;
//返回一个0到values的长度之间的随机数
let random = Math.floor(Math.random() * size);
//以随机数为下标返回
return this.values[random];
}; |
insert有问题吧，insert 的时候如果有已经存在，按照题目要求返回false，为什么要用数组把它们下标都存下来 |
不好意思，没看清，已改，谢谢指出 @luweiCN |
解答一：Map+数组const RandomizedSet = function() {
this.map = new Map()
this.values = []
};
RandomizedSet.prototype.insert = function(val) {
// 存在
if(this.map.has(val)) {
return false
}
// 不存在
this.map.set(val, this.values.length)
this.values.push(val)
return true
};
RandomizedSet.prototype.remove = function(val) {
// 不存在
if(!this.map.has(val)) {
return false
}
const index = this.map.get(val)
// 存在且为最后一个元素
if(index === this.values.length - 1) {
this.values.pop()
this.map.delete(val)
} else { // 存在不为最后一个元素
const lastValue = this.values.pop()
this.values[index] = lastValue
this.map.set(lastValue, index)
this.map.delete(val)
}
return true
};
RandomizedSet.prototype.getRandom = function() {
const length = this.values.length
const random = Math.floor(Math.random() * length)
return this.values[random];
};解答二：也可以使用Setconst RandomizedSet = function() {
this.set = new Set()
}
RandomizedSet.prototype.insert = function(val) {
if (this.set.has(val)) {
return false
}
this.set.add(val)
return true
}
RandomizedSet.prototype.remove = function(val) {
if (!this.set.has(val)) {
return false
}
this.set.delete(val)
return true
}
RandomizedSet.prototype.getRandom = function() {
const random = parseInt(Math.random()*(this.set.size))
return [...this.set][random]
} |
var RandomizedSet = function() {
this.hashMap = new Map();
this.arr = [];
}
/**
* Inserts a value to the set. Returns true if the set did not already contain the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.insert = function(val) {
if (this.hashMap.has(val)) {
return false
} else {
this.hashMap.set(val, this.arr.length);
this.arr.push(val);
return true
}
};
/**
* Removes a value from the set. Returns true if the set contained the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.remove = function(val) {
var delIndex = this.hashMap.get(val);
if (delIndex === undefined) {
return false;
} else {
var lastNum = this.arr[this.arr.length - 1];
this.arr[delIndex] = lastNum;
this.hashMap.set(lastNum, delIndex);
this.arr.pop();
return this.hashMap.delete(val);
}
};
/**
* Get a random element from the set.
* @return {number}
*/
RandomizedSet.prototype.getRandom = function() {
var random = Math.floor(Math.random() * this.arr.length);
return this.arr[random];
}; |
|
/**
* Initialize your data structure here.
*/
var RandomizedSet = function () {
this.hash = {};
this.arr = [];
};
/**
* Inserts a value to the set. Returns true if the set did not already contain the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.insert = function (val) {
// 如果存在返回false
if (this.hash[val] !== undefined) {
return false;
} else {
// 如果不存在hash表中，将其加入arr中，并数之hash以val为键的值为当前index
this.arr.push(val);
this.hash[val] = this.arr.length - 1; // 其实就是当前值在数组中的index
return true;
}
};
/**
* Removes a value from the set. Returns true if the set contained the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.remove = function (val) {
// 存在才删除
if (this.hash[val] !== undefined) {
// 交换当前值与数组末尾元素
[this.arr[this.hash[val]], this.arr[this.arr.length - 1]] = [this.arr[this.arr.length - 1], this.arr[this.hash[val]]];
// 更改末尾元素的index
this.hash[this.arr[this.hash[val]]] = this.hash[val];
// 清除末尾元素
this.arr.pop();
// 删除hash表中的值
delete this.hash[val];
return true;
} else {
return false;
}
};
/**
* Get a random element from the set.
* @return {number}
*/
RandomizedSet.prototype.getRandom = function () {
return this.arr[Math.random()*(this.arr.length) | 0];
};
/**
* Your RandomizedSet object will be instantiated and called as such:
* var obj = new RandomizedSet()
* var param_1 = obj.insert(val)
* var param_2 = obj.remove(val)
* var param_3 = obj.getRandom()
*/ |
题目地址（380. 常数时间插入、删除和获取随机元素）https://leetcode-cn.com/problems/insert-delete-getrandom-o1/description/ 题目描述思路这是一个设计题。这道题的核心就是考察基本数据结构和算法的操作以及复杂度。 我们来回顾一下基础知识：
由于题目要求 getRandom 返回要随机并且要在$O(1)$复杂度内，那么如果单纯使用链表或者哈希表肯定是不行的。 而又由于对于插入和删除也需要复杂度为$O(1)$，因此单纯使用数组也是不行的，因此考虑多种使用数据结构来实现。
对于 getRandom 用数组很简单。对于判断是否已经有了存在的元素，我们使用哈希表也很容易做到。因此我们可以将数组随机访问，以及哈希表$O(1)$按检索值的特性结合起来，即同时使用这两种数据结构。 对于删除和插入，我们需要一些技巧。 对于插入：
因此如何应付删除的这种性能开销呢？ 我们知道对于数据删除，我们的时间复杂度来源于
对于 1，我们可以通过哈希表来实现。 key 是插入的数字，value 是数组对应的索引。删除的时候我们根据 key 反查出索引就可以快速找到。
对于 2，我们可以通过和数组最后一项进行交换的方式来实现，这样就避免了数据移动。同时数组其他项的索引仍然保持不变，非常好！
图解： 以依次【1，2，3，4】之后为初始状态，那么此时状态是这样的： 而当要插入一个新的 5 的时候， 我们只需要分别向数组末尾和哈希表中插入这条记录即可。 而删除的时候稍微有一点复杂： 关键点解析
代码from random import random
class RandomizedSet:
def __init__(self):
"""
Initialize your data structure here.
"""
self.data = dict()
self.arr = []
self.n = 0
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.data:
return False
self.data[val] = self.n
self.arr.append(val)
self.n += 1
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.data:
return False
i = self.data[val]
# 更新data
self.data[self.arr[-1]] = i
self.data.pop(val)
# 更新arr
self.arr[i] = self.arr[-1]
# 删除最后一项
self.arr.pop()
self.n -= 1
return True
def getRandom(self) -> int:
"""
Get a random element from the set.
"""
return self.arr[int(random() * self.n)]
# 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()复杂度分析
更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。 大家也可以关注我的公众号《力扣加加》获取更多更新鲜的 LeetCode 题解 |
|
为什么都用 class RandomizedSet {
private mapValueToIndex: Record<number, number> = {};
private mapIndexToValue: Record<number, number> = {};
public length: number = 0;
insert (data: number) {
if (this.mapValueToIndex[data] !== undefined) return false;
this.mapValueToIndex[data] = this.length;
this.mapIndexToValue[this.length] = data;
this.length++;
return true;
}
remove (data: number) {
const removeDataIndex = this.mapValueToIndex[data];
if (removeDataIndex === undefined) return false;
delete this.mapValueToIndex[data];
delete this.mapIndexToValue[removeDataIndex];
this.length--;
return true;
}
getRandom () {
const randomIndex = Math.floor(this.length * Math.random());
return this.mapIndexToValue[randomIndex];
}
}
const randomSet = new RandomizedSet();
console.log(randomSet.insert(1));
console.log(randomSet.remove(2));
console.log(randomSet.insert(2));
console.log(randomSet.getRandom());
console.log(randomSet.remove(1));
console.log(randomSet.insert(2));
console.log(randomSet);
// 输出
// true
// false
// true
// 1 或者 2
// true
// false
// RandomizedSet {
// mapValueToIndex: { '2': 1 },
// mapIndexToValue: { '1': 2 },
// length: 1
// } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。
insert(val)：当元素 val 不存在时，向集合中插入该项。remove(val)：元素 val 存在时，从集合中移除该项。getRandom：随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。示例 :
附赠leetcode地址：leetcode
The text was updated successfully, but these errors were encountered: