380.o-1-时间插入、删除和获取随机元素.md

380.o-1-时间插入、删除和获取随机元素

/*
 * @lc app=leetcode.cn id=380 lang=typescript
 *
 * [380] O(1) 时间插入、删除和获取随机元素
 */

// @lc code=start
class RandomizedSet {
  constructor() {}

  insert(val: number): boolean {}

  remove(val: number): boolean {}

  getRandom(): number {}
}

/**
 * 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()
 */
// @lc code=end

解法 1: 数组 + 哈希表

class RandomizedSet {
  private arr: number[] = []
  private map = new Map<number, number>()
  private index = 0
  constructor() {}

  insert(val: number): boolean {
    if (this.map.has(val)) return false
    this.map.set(val, this.index)
    this.arr[this.index++] = val
    return true
  }

  remove(val: number): boolean {
    const { map, arr, index } = this
    if (!map.has(val)) return false
    const i = map.get(val)!
    arr[i] = arr[--this.index]
    map.set(arr[i], i)
    map.delete(val)
    return true
  }

  getRandom(): number {
    const i = Math.floor(Math.random() * this.index)
    console.log(i, this.index, this.arr)
    return this.arr[i]
  }
}