# 380. Insert Delete GetRandom O(1)


### Idea

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

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`