题目

题目来源：力扣（LeetCode）

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

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

示例 :

  1. // 初始化一个空的集合。
  2. RandomizedSet randomSet = new RandomizedSet();
  4. // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
  5. randomSet.insert(1);
  7. // 返回 false ，表示集合中不存在 2 。
  8. randomSet.remove(2);
  10. // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
  11. randomSet.insert(2);
  13. // getRandom 应随机返回 1 或 2 。
  14. randomSet.getRandom();
  16. // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
  17. randomSet.remove(1);
  19. // 2 已在集合中，所以返回 false 。
  20. randomSet.insert(2);
  22. // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
  23. randomSet.getRandom();

思路分析

数组 + 哈希表

数组存储值，在 gerRandom 时可以获得真正的随机值，哈希表存储值到索引的映射关系，可以在常数时间内获取到要删除元素的索引。

因此，我们使用以下的数据结构：

  • 动态数组存储元素值
  • 哈希表存储值到索引的映射
    1. var RandomizedSet = function() {
    2. // 存储值和索引的对应关系
    3. this.map= new Map();
    4. // 存储值
    5. this.list = [];
    6. };

insert 操作时

若元素不存在：

  • 将元素添加到动态数组
  • 在哈希表中添加值到索引的映射
  • 最后返回 true

若元素已存在：

  • 返回false

    1. RandomizedSet.prototype.insert = function(val) {
    2. if (!this.map.has(val)) return false;
    4. this.list.push(val);
    5. this.map.set(val, this.list.length - 1);
    6. return true;
    7. };

remove 操作时

若元素不存在：

  • 返回false

若元素存在：

  • 在哈希表中查找要删除元素的索引
  • 将要删除元素与最后一个元素交换
  • 删除最后一个元素
  • 更新哈希表中的对应关系
  • 最后返回 true ```javascript RandomizedSet.prototype.remove = function(val) { if (!this.map.has(val)) return false; // 在哈希表中查找要删除元素的索引 const index = this.map.get(val); const len = this.list.length - 1; // 将要删除元素与最后一个元素交换 [this.list[index], this.list[len]] = [this.list[len], this.list[index]]; // 更新哈希表中的对应关系 this.map.set(rhis.list[index], index); // 删除列表中的最后一个元素 this.list.pop(); // 删除哈希表中当前已删除元素的对应关系 this.map.delete(val); return true;

};

  2. **getRandom 操作时**
  4. 借助 Math.random * list.length 与 0 做位运算，获取随机索引
  5. ```javascript
  6. RandomizedSet.prototype.getRandom = function() {
  7.   //  | 位运算符 OR, 一对数位执行位运算 OR 时，如果其中一位是 1 则返回 1
  8.   // 0 | 0 结果为 0
  9.   // 0 | 1 结果为 1
  10.   // 1 | 0 结果为 1
  11.   // 1 | 1 结果为 1
  12.   // Math.random() * this.list.length | 0  获取随机索引
  13.   return this.list[Math.random() * this.list.length | 0];
  14. };

完整代码

  1. /**
  2.  * Initialize your data structure here.
  3.  */
  4.  var RandomizedSet = function() {
  5.   // 存储值和索引的对应关系
  6.   this.map= new Map();
  7.   // 存储值
  8.   this.list = [];
  9. };
  11. /**
  12.  * Inserts a value to the set. Returns true if the set did not already contain the specified element. 
  13.  * @param {number} val
  14.  * @return {boolean}
  15.  */
  16. RandomizedSet.prototype.insert = function(val) {
  17.   // 元素已在集合中，返回 false
  18.   if (this.map.has(val)) return false;
  20.   // 向集合中插入元素，并返回 true
  21.   this.list.push(val);
  22.   this.map.set(val, this.list.length - 1);
  23.   return true;
  24. };
  26. /**
  27.  * Removes a value from the set. Returns true if the set contained the specified element. 
  28.  * @param {number} val
  29.  * @return {boolean}
  30.  */
  31. RandomizedSet.prototype.remove = function(val) {
  32.   // 当前要删除的元素不在集合中，返回 false
  33.   if (!this.map.has(val)) return false;
  35.   // 在哈希表中查找要删除元素的索引
  36.   const index = this.map.get(val);
  37.   const len = this.list.length - 1;
  38.   // 将要删除元素与最后一个元素交换
  39.   [this.list[index], this.list[len]] = [this.list[len], this.list[index]];
  40.   // 更新哈希表中的对应关系
  41.   this.map.set(this.list[index], index);
  42.   // 删除列表中的最后一个元素
  43.   this.list.pop();
  44.   // 删除哈希表中当前已删除元素的对应关系
  45.   this.map.delete(val);
  46.   return true;
  48. };
  50. /**
  51.  * Get a random element from the set.
  52.  * @return {number}
  53.  */
  54. RandomizedSet.prototype.getRandom = function() {
  55.   //  | 位运算符 OR, 一对数位执行位运算 OR 时，如果其中一位是 1 则返回 1
  56.   // 0 | 0 结果为 0
  57.   // 0 | 1 结果为 1
  58.   // 1 | 0 结果为 1
  59.   // 1 | 1 结果为 1
  60.   // Math.random() * this.list.length | 0  获取随机索引
  61.   return this.list[Math.random() * this.list.length | 0];
  62. };
  64. /**
  65.  * Your RandomizedSet object will be instantiated and called as such:
  66.  * var obj = new RandomizedSet()
  67.  * var param_1 = obj.insert(val)
  68.  * var param_2 = obj.remove(val)
  69.  * var param_3 = obj.getRandom()
  70.  */