iOS LeetCode ☞ O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类：

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

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

示例：

输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

提示：

• -2³¹ <= val <= 2³¹ - 1
• 最多调用 insert、remove 和 getRandom 函数 2 * 10⁵ 次
  在调用 getRandom 方法时，数据结构中 至少存在一个 元素。

我们需要在平均复杂度为 O(1) 实现以下操作：

1. insert
2. remove
3. getRadom

让我们想想如何实现它。从 insert 开始，我们具有两个平均插入时间为 O(1) 的选择：

• 哈希表：Java 中为 HashMap，Python 中为 dictionary。
• 动态数组：Java 中为 ArrayList，Python 中为 list。

让我们一个个进行思考，虽然哈希表提供常数时间的插入和删除，但是实现 getRandom 时会出现问题。

getRandom 的思想是选择一个随机索引，然后使用该索引返回一个元素。而哈希表中没有索引，因此要获得真正的随机值，则要将哈希表中的键转换为列表，这需要线性时间。解决的方法是用一个列表存储值，并在该列表中实现常数时间的 getRandom。

列表有索引可以实现常数时间的 insert 和 getRandom，则接下来的问题是如何实现常数时间的 remove。

删除任意索引元素需要线性时间，这里的解决方案是总是删除最后一个元素。

• 将要删除元素和最后一个元素交换。
• 将最后一个元素删除。

为此，必须在常数时间获取到要删除元素的索引，因此需要一个哈希表来存储值到索引的映射。

综上所述，我们使用以下数据结构：

• 动态数组存储元素值
• 哈希表存储存储值到索引的映射。

// 380. O(1)时间插入、删除和获取随机元素
class RandomizedSet {

    var list: [Int]
    var dict: [Int: Int]
    
    init() {
        list = [Int]()
        dict = [Int: Int]()
    }
    
    func insert(_ val: Int) -> Bool {
        if let _ = dict[val] {
            return false
        }
        dict[val] = list.count
        list.append(val)
        return true
    }
    
    func remove(_ val: Int) -> Bool {
        guard let index = dict[val] else {
            return false
        }
        
        if index != list.count - 1 {
            let lastVal = list.last!
            dict[lastVal] = index
            list.swapAt(index, list.count - 1)
        }
        list.removeLast()
        dict.removevalue(forKey: val)
        return true
    }
    
    func getRandom() -> Int {
        return list[Int.random(in: 0..