380. Insert Delete GetRandom O(1)

Idea

題目要求設計一個插入、刪除、跟取隨機都要 O(1) 的類別 RandomizedSet。
先針對每個操作單純思考，用最直覺的資料型態個別解決單一一個操作看看。

1. insert 要做到 O(1) 可以用 Map ( key 為輸入值)
2. getRandom 要做到 O(1) 可以用 Array (value 為輸入值)
3. delete 要做到 O(1) 可以用 Map (key 為輸入值)

經過上述的直覺思考，我們的 getRandom 跟 insert 大致上想法沒毛病，只需要一個存輸入值的 Array 跟一個以輸入值為 key 、 ???為 value 的 Map 就有可能實現。 那個 ??? 究竟該存什麼才能把 delete 也一起解決呢？

記憶當前 Array 的位置 (index)，會這麼思考是因為如果我每次插入時，Array 新增一個輸入值，Map 也以輸入值為 key 、位置為 value，這樣的話 delete 時就能直接從 Map 抓到這個輸入值在 Array 中的位置，把它跟 Array 最後一個元素做調換再 pop 掉只需要 O(1)，之後把 Map 更新位置資訊，刪除輸入值的 key，即可達成無痛刪除。

export class RandomizedSet {
  constructor() {
    this.map = new Map()
    this.keys = new Array()
  }
  insert(val) {
    if (this.map.has(val)) return false
    this.keys.push(val)
    this.map.set(val, this.keys.length - 1)
    return true
  }
  remove(val) {
    if (!this.map.has(val)) return false
    const idx = this.map.get(val)
    const last = this.keys[this.keys.length - 1]
    this.keys[idx] = last
    this.map.set(last, idx)
    this.map.delete(val)
    this.keys.pop()
    return true
  }
  getRandom() {
    const idx = Math.floor(Math.random() * this.keys.length)
    return this.keys[idx]
  }
}

tags: Leetcode JavaScript