如何在数组中以 O(1) 删除元素 (opens new window)

1. 数组 O(1)删除，利用交换最后一项元素，进行删除。

2. 使用 Map 建立数组索引

var RandomizedSet = function () {
  this.map = new Map()
  this.arr = new Array()
}

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function (val) {
  // 将 val 作为key  当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
  if (this.map.has(val)) {
    return false
  } else {
    const index = this.arr.length
    this.arr.push(val)
    this.map.set(val, index)
    return true
  }
}

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function (val) {
  // remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false
  if (!this.map.has(val)) {
    return false
  } else {
    // 找到在数组中的索引 O(1)的方式去掉这个值 交换索引然后pop
    const index = this.map.get(val)
    const lastIndex = this.arr.length - 1
    ;[this.arr[index], this.arr[lastIndex]] = [this.arr[lastIndex], this.arr[index]]
    // 将最后一个数转移出来 更新这个转移出来的ID的值
    this.map.set(this.arr[index], index)

    this.arr.pop()
    this.map.delete(val)
    return true
  }
}

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function () {
  const random = Math.floor(Math.random() * this.arr.length)
  return this.arr[random]
}