O(1)时间插入删除和获取随机元素.md

380. O(1) 时间插入、删除和获取随机元素

/**
 * Initialize your data structure here.
 */
var RandomizedSet = function () {
  // 初始化数据 hashMap 查找  elems 保存数据
  this.hashMap = new Map();
  this.elems = [];
};

/**
 * 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;
  }
  // 不存在
  this.hashMap.set(val, this.elems.length);
  this.elems.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) {
  // 不存在直接返回 false
  if (!this.hashMap.has(val)) {
    return false;
  }

  // 获取 当前值的下标
  let index = this.hashMap.get(val);

  // 如果下标对应的是最后的位置
  if (index === this.elems.length - 1) {
    this.elems.pop();
    this.hashMap.delete(val);
  } else {
    // 否则将最后一位的值与当前值交换 完成删除
    const last = this.elems.pop();
    this.elems[index] = last;
    this.hashMap.set(last, index);
    this.hashMap.delete(val);
  }

  return true;
};

/**
 * Get a random element from the set.
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function () {
  const len = this.elems.length;
  const random = Math.floor(Math.random() * len);

  return this.elems[random];
};

/**
 * 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()
 */