Skip to main content

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

题目​

实现 `RandomizedSet`` 类:

  • RandomizedSet() 初始化 RandomizedSet 对象
  • bool insert(int val) 当元素 val 不存在时, 向集合中插入该项, 并返回 true; 否则, 返回 false.
  • bool remove(int val) 当元素 val 存在时, 从集合中移除该项, 并返回 true; 否则, 返回 false.
  • int getRandom() 随机返回现有集合中的一项(测试用例保证调用此方法时集合中至少存在一个元素). 每个元素应该有相同的概率返回.

要求以上三个方法都是 O(1) 时间复杂度.

题解​

对于 insert 和 remove 操作容易想到使用哈希表来实现 O(1) 复杂度, 但对于 getRandom 操作, 比较理想的情况是能够在一个数组内随机下标进行返回.

var RandomizedSet = function () {
  // 维护一个 map, key 是 val, value 为 idx
  this.map = new Map()
  // 将数据存储到一个数组, 便于随机获取.
  this.nums = []
}

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function (val) {
  if (this.map.has(val)) return false

  this.map.set(val, this.nums.length)
  this.nums.push(val)
  return true
}

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function (val) {
  if (!this.map.has(val)) return false

  const idx = this.map.get(val)
  // 将数组的最后一个元素复写到 idx 的位置, 这样保证在数组中把 val 删除掉了
  this.nums[idx] = this.nums[this.nums.length - 1]
  // 此时数组最后一个元素没用了, pop 掉
  this.nums.pop()
  // 在 map 中将 val 移除
  this.map.delete(val)
  // 由于最后一个元素改变了位置(this.nums.length - 1 -> idx), 需要更新最后一个元素在 map 中的 value
  this.map.set(this.nums[idx], idx)
  
  return true
}

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function () {
  const randomIdx = Math.floor(Math.random() * this.nums.length)
  return this.nums[randomIdx]
}

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