Pengjielee's blog

题目

设计一个支持在平均时间复杂度 O(1) 下，执行以下操作的数据结构。

insert(val)：当元素 val 不存在时，向集合中插入该项。
remove(val)：元素 val 存在时，从集合中移除该项。
getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

示例 :

// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中，所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

参考代码1：

/**
 * Initialize your data structure here.
 */
var RandomizedSet = function () {
  this.array = [];
  this.map = new Map();
};

/**
 * Inserts a value to the set. Returns true if the set did not already contain the specified element.
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function (val) {
  if (this.map.has(val)) {
    return false;
  }
  //添加元素到数组
  this.array.push(val);
  //哈希表存储 值到索引 的映射
  this.map.set(val, this.size() - 1);
  return true;
};

/**
 * Removes a value from the set. Returns true if the set contained the specified element.
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function (val) {
  if (!this.map.has(val)) {
    return false;
  }
  const index = this.map.get(val);
  const lastIndex = this.size() - 1;
  //交换该元素到数组末尾
  if (index < lastIndex) {
    const last = this.array[lastIndex];
    this.array[lastIndex] = this.array[index];
    this.array[index] = last;
    //更新交换后元素的下标
    this.map.set(this.array[index], index);
  }
  //删除数组末尾元素
  this.array.pop();
  //删除map存储的【值-下标】映射
  this.map.delete(val);
  return true;
};

/**
 * Get a random element from the set.
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function () {
  const len = this.size();
  if (len === 0) {
    return false;
  }
  const randomIndex = Math.floor(Math.random() * len);
  return this.array[randomIndex];
};

RandomizedSet.prototype.size = function () {
  return this.array.length;
};

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

参考代码2：

class RandomizedSet {
  constructor() {
    // store the actual values
    this.array = [];
    // store the value-> index mapping
    this.map = {};
  }

  insert(val) {
    if (val in this.map) return false;
    this.array.push(val);
    this.map[val] = this._size() - 1;
    return true;
  }

  remove(val) {
    if (!(val in this.map)) return false;

    const index = this.map[val];
    const lastIndex = this._size() - 1;
    if (index < lastIndex) {
      this._swap(index, lastIndex);
      this.map[this.array[index]] = index;
    }
    this.array.pop();
    delete this.map[val];
    return true;
  }

  getRandom() {
    const size = this._size();
    if (size === 0) return false;
    let randomIndex = Math.floor(Math.random() * size);
    return this.array[randomIndex];
  }

  _size() {
    return this.array.length;
  }

  _swap(a, b) {
    const temp = this.array[b];
    this.array[b] = this.array[a];
    this.array[a] = temp;
  }
}

作者：suukii 链接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1/solution/tu-jie-chang-shu-shi-jian-cha-ru-shan-chu-he-huo-q/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。