题目

设计一个支持在平均 时间复杂度 常数时间插入、删除和获取随机元素 - 图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();

方案一

  1. type RandomizedSet struct {
  2.     m map[int]int
  3. }
  6. /** Initialize your data structure here. */
  7. func Constructor() RandomizedSet {
  8.     return RandomizedSet {
  9.         m: map[int]int{},
  10.     }
  11. }
  14. /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
  15. func (this *RandomizedSet) Insert(val int) bool {
  16.     if _, ok := this.m[val]; ok {
  17.         return false
  18.     }
  19.     this.m[val] = 0
  20.     return true
  21. }
  24. /** Removes a value from the set. Returns true if the set contained the specified element. */
  25. func (this *RandomizedSet) Remove(val int) bool {
  26.     if _, ok := this.m[val]; !ok {
  27.         return false
  28.     }
  29.     delete(this.m, val)
  30.     return true
  31. }
  34. /** Get a random element from the set. */
  35. func (this *RandomizedSet) GetRandom() int {
  36.     keys := []int{}
  37.     for k, _ := range this.m {
  38.         keys = append(keys, k)
  39.     }
  41.     return keys[rand.Intn(len(keys))]
  42. }
  • 上述方案获取随机值时间复杂度为 常数时间插入、删除和获取随机元素 - 图2

方案二

type RandomizedSet struct {
    list []int
    m map[int]int // value: list index -> 让我想到了 lru的实现，即使用 map + 双向链表的思路
}


/** Initialize your data structure here. */
func Constructor() RandomizedSet {
    return RandomizedSet {
        list: []int{},
        m: map[int]int{}, // key: val, value: 对应 list 的 index
    }
}


/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
func (this *RandomizedSet) Insert(val int) bool {
    if _, ok := this.m[val]; ok {
        return false
    }
    this.m[val] = len(this.list)
    this.list = append(this.list, val)
    return true
}


/** Removes a value from the set. Returns true if the set contained the specified element. */
func (this *RandomizedSet) Remove(val int) bool {
    index, ok := this.m[val]
    if !ok {
        return false
    }
    if index != len(this.list) - 1 { // 删除的不是数组的最后一个；这时为了防止删除导致数组元素移动以及 this.m 索引问题，采用交换的策略
        last := this.list[len(this.list) - 1]
        this.list[index] = last
        this.m[last] = index
    }

    // 删除数组最后一个元素
    this.list = this.list[:len(this.list) - 1]
    delete(this.m, val)
    return true
}


/** Get a random element from the set. */
func (this *RandomizedSet) GetRandom() int {
    return this.list[rand.Intn(len(this.list))]
}
  • 使用一个 map 来存储实际数据的指针，同时使用另一个列表来存储实际数据
  • 注意 Remove 方法采取的方案。——交换，避免不必要的元素移动

原文

https://leetcode-cn.com/explore/learn/card/hash-table/207/conclusion/831/