51 lines
1.6 KiB
JavaScript
51 lines
1.6 KiB
JavaScript
// O(1) 时间插入、删除和获取随机元素
|
||
// 学习目标，利用哈希表和动态数组实现高效数据结构
|
||
|
||
const RandomizedSet = function () {
|
||
this.nums = [];// 动态数组，储存真实数据，目的是实现O(1)时间内返回随机数据
|
||
this.valToIndex = new Map(); // 哈希表，实现O(1)时间内查找，删除，插入
|
||
};
|
||
|
||
/**
|
||
* @param {number} val
|
||
* @return {boolean}
|
||
*/
|
||
RandomizedSet.prototype.insert = function (val) {
|
||
// 先判断插入的数据是否已经存在，如果存在直接返回false
|
||
if (this.valToIndex.has(val)) return false;
|
||
// 维护插入数据的下标
|
||
this.valToIndex.set(val, this.nums.length);
|
||
this.nums.push(val);
|
||
return true;
|
||
};
|
||
|
||
/**
|
||
* @param {number} val
|
||
* @return {boolean}
|
||
*/
|
||
RandomizedSet.prototype.remove = function (val) {
|
||
// 先判断元素是否存在，如果不存在就返回false
|
||
if (!this.valToIndex.has(val)) return false;
|
||
// 获取当前元素和最后一个元素的下标
|
||
const index = this.valToIndex.get(val);
|
||
const lastVal = this.nums[this.nums.length - 1];
|
||
// 把最后一个元素覆盖到当前位置
|
||
this.nums[index] = lastVal;
|
||
// 更新原本最后一个元素在哈希表中维持的位置
|
||
this.valToIndex.set(lastVal, index);
|
||
// 删除最后一个位置的数据
|
||
this.nums.pop();
|
||
// 删除当前元素在哈希表中维持的位置
|
||
this.valToIndex.delete(val);
|
||
return true;
|
||
};
|
||
|
||
/**
|
||
* @return {number}
|
||
*/
|
||
RandomizedSet.prototype.getRandom = function () {
|
||
// 引入动态数组的目的就是为了实现O(1)返回随机数据
|
||
const randomIndex = Math.floor(Math.random() * this.nums.length);
|
||
return this.nums[randomIndex];
|
||
};
|