实现RandomizedSet 类：
RandomizedSet()初始化RandomizedSet对象bool insert(int val)当元素val不存在时，向集合中插入该项，并返回true；否则，返回false。bool remove(int val)当元素val存在时，从集合中移除该项，并返回true；否则，返回false。int getRandom()随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
- \(-2^31\) <= val <= \(2^31 - 1\)
- 最多调用
insert、remove和getRandom函数 \(2 * 10^5\) 次 - 在调用
getRandom方法时，数据结构中 至少存在一个 元素。
var RandomizedSet = function () {
};
/**
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.insert = function (val) {
};
/**
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.remove = function (val) {
};
/**
* @return {number}
*/
RandomizedSet.prototype.getRandom = function () {
};
/**
* 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()
*/
要求是对集合中元素的插入、删除、随机获取的操作都是 O(1) 时间复杂度。考虑使用数组、Map、Set。
方法1：数组结合Map
数组的 push、pop都是 O(1) 时间复杂度，但数组根据索引获取值，所以使用 Map 存储 value-index 的键值对。
这样，就能使用 Map 检查元素是否存在。
删除时，如果元素存在，获取它的下标，用数组最后一个元素替换它，然后使用 pop 删除最后一个元素，相当于删除了它，更新 Map。
插入时，如果元素不存在，更新数组和 Map。
获取随机值时，使用 Math.random 产生随机下标。
var RandomizedSet = function () {
// 数组
this.values = [];
// 值到索引的 Map 映射
this.valueToIndex = new Map();
};
/**
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.insert = function (val) {
if (this.valueToIndex.has(val)) {
return false;
}
this.values.push(val);
this.valueToIndex.set(val, this.values.length - 1);
return true;
};
/**
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.remove = function (val) {
if (!this.valueToIndex.has(val)) {
return false;
}
let index = this.valueToIndex.get(val);
let last = this.values[this.values.length - 1];
this.values[index] = last;
this.valueToIndex.set(last, index);
this.values.pop();
this.valueToIndex.delete(val);
return true;
};
/**
* @return {number}
*/
RandomizedSet.prototype.getRandom = function () {
const randomIndex = Math.floor(Math.random() * this.values.length);
return this.values[randomIndex];
};
/**
* 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()
*/
方法2：使用 set
set 的 add 和 delete 方法都很方便。
唯独获取随机值这个需要考虑。
我们可以使用 Array.from() 将 set 转为数组。
var RandomizedSet = function () {
this.set = new Set();
};
/**
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.insert = function (val) {
if (this.set.has(val)) {
return false;
}
this.set.add(val);
return true;
};
/**
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.remove = function (val) {
if (!this.set.has(val)) {
return false;
}
this.set.delete(val);
return true;
};
/**
* @return {number}
*/
RandomizedSet.prototype.getRandom = function () {
const values = Array.from(this.set);
const randomIndex = Math.floor(Math.random() * values.length);
return values[randomIndex];
};
使用 set 的迭代器：
RandomizedSet.prototype.getRandom = function() {
const values = Array.from(this.set);
const randomIndex = Math.floor(Math.random() * this.set.size);
const iterator = this.set.values();
for (let i = 0; i < randomIndex; i++) {
iterator.next();
}
return iterator.next().value;
};