380. Insert Delete GetRandom O(1)

🟠   🔖  设计 数组 哈希表 数学 随机化  🔗 LeetCode

题目

Implement the RandomizedSet class:

• RandomizedSet() Initializes the RandomizedSet object.
• bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
• bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
• int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Example 1:

Input

["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]

[[], [1], [2], [2], [], [1], [2], []]

Output

[null, true, false, true, 2, true, false, 2]

Explanation

RandomizedSet randomizedSet = new RandomizedSet();

randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.

randomizedSet.remove(2); // Returns false as 2 does not exist in the set.

randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].

randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.

randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].

randomizedSet.insert(2); // 2 was already in the set, so return false.

randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Constraints:

• -2^31 <= val <= 2^31 - 1
• At most 2 * ``105 calls will be made to insert, remove, and getRandom.
• There will be at least one element in the data structure when getRandom is called.

题目大意

实现 RandomizedSet 类：

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

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

解题思路

本题的难点在于两点：

1. 插入，删除，获取随机元素这三个操作的时间复杂度必须都是 O(1)。
2. getRandom 方法返回的元素必须等概率返回随机元素，也就是说，如果集合里面有 n 个元素，每个元素被返回的概率必须是 1/n。

HashSet 插入，删除，查找这几种操作的时间复杂度是 O(1) ，但是由于HashSet存储数据时，是由哈希函数分散地存到整个数组里面的，遇到哈希冲突还会有拉链法等机制，所以做不到 O(1) 时间「等概率」随机获取元素。

如果想「等概率」且「在 O(1) 的时间」取出元素，一定要满足：底层用数组实现，且数组必须是紧凑的。可以直接生成随机数作为索引，从数组中取出该随机索引对应的元素，作为随机元素。

但如果用数组存储元素的话，插入，删除的时间复杂度怎么做到 O(1) 呢？

由于对数组尾部进行插入和删除操作时不会涉及数据搬移，时间复杂度是 O(1)，所以：

• 插入数据时直接插入到数组尾端即可；
• 删除数组中的某一个元素时，先把这个元素交换到数组的尾部，然后再 pop 掉，交换两个元素时通过索引进行交换，用一个哈希表 indexMap 来记录每个元素值对应的索引。

代码

class RandomizedSet {
  constructor() {
    this.nums = [];
    this.map = new Map();
  }

  // @param {number} val
  // @return {boolean}
  insert(val) {
    if (this.map.has(val)) return false;
    this.nums.push(val);
    this.map.set(val, this.nums.length - 1);
    return true;
  }

  // @param {number} val
  // @return {boolean}
  remove(val) {
    if (!this.map.has(val)) return false;
    const index = this.map.get(val);
    const last_val = this.nums[this.nums.length - 1];
    this.nums[index] = last_val;
    this.nums.pop();
    this.map.set(last_val, index);
    this.map.delete(val);
    return true;
  }

  // @return {number}
  getRandom() {
    return this.nums[Math.floor(Math.random() * this.nums.length)];
  }
}

相关题目

相关题目

• 381. O(1) 时间插入、删除和获取随机元素 - 允许重复

- [381. O(1) 时间插入、删除和获取随机元素 - 允许重复](https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed)