Lstmxx的空间

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

实现 RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

class RandomizedSet {
    nums: number[];
    map: Map<number,number>;
    constructor() {
      this.map = new Map();
      this.nums = [];
    }

    insert(val: number): boolean {
      if (this.map.has(val)) {
        return false;
      }
      const lastIndex = this.nums.length;
      this.nums.push(val);
      this.map.set(val, lastIndex);
      return true;
    }

    remove(val: number): boolean {
      const index = this.map.get(val);
      if (index === undefined) {
        return false;
      }
      this.nums[index] = this.nums[this.nums.length - 1];
      this.map.set(this.nums[index], index);
      this.nums.pop();
      this.map.delete(val);
      return true;
    }

    getRandom(): number {
      const index = Math.floor(Math.random() * this.nums.length);
      return this.nums[index];
    }
}

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