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

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

描述

题目要求实现 RandomizedSet 类，支持以下操作：

1. RandomizedSet()：初始化对象。
2. bool insert(int val)：当元素 val 不存在时插入，返回 true；否则返回 false。
3. bool remove(int val)：当元素 val 存在时移除，返回 true；否则返回 false。
4. 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。
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^31 <= val <= 2^31 - 1
• 最多调用 insert、remove 和 getRandom 函数 2 * 10^5 次
• 在调用 getRandom 方法时，数据结构中至少存在一个元素

核心思路是使用数组和字典：数组用来存储元素，支持 O(1) 的随机访问；字典用来存储元素到索引的映射，支持 O(1) 的查找和删除。删除时，将最后一个元素移到被删除元素的位置，然后删除最后一个元素，保证 O(1) 的删除操作。

题解答案

下面是完整的 Swift 解决方案：

class RandomizedSet {
    // 数组：存储所有元素，支持 O(1) 随机访问
    private var array: [Int]
    // 字典：存储元素到索引的映射，支持 O(1) 查找和删除
    private var dict: [Int: Int]
    
    init() {
        self.array = []
        self.dict = [:]
    }
    
    /// 插入元素
    func insert(_ val: Int) -> Bool {
        // 如果元素已存在，返回 false
        if dict[val] != nil {
            return false
        }
        // 将元素添加到数组末尾
        array.append(val)
        // 记录元素在数组中的索引
        dict[val] = array.count - 1
        return true
    }
    
    /// 删除元素
    func remove(_ val: Int) -> Bool {
        // 如果元素不存在，返回 false
        guard let index = dict[val] else {
            return false
        }
        // 获取数组最后一个元素
        let lastElement  array[array.count  ]
        
        array[index]  lastElement
        
        dict[lastElement]  index
        
        array.removeLast()
        
        dict.removeValue(forKey: val)
         
    }
    
    
     () ->  {
        
         randomIndex  .random(in: array.count)
         array[randomIndex]
    }
}

题解代码分析

1. 数据结构的选择

我们使用了两个数据结构：

• array：一个数组，用来存储所有元素。数组支持 O(1) 的随机访问，这对于 getRandom() 操作非常重要。
• dict：一个字典，用来存储元素到索引的映射。字典支持 O(1) 的查找和删除，这对于 insert() 和 remove() 操作非常重要。

2. 为什么需要两个数据结构？

• 只用数组：insert() 是 O(1)，但 remove() 是 O(n)（需要查找并移动元素），getRandom() 是 O(1)。
• 只用 Set：insert() 和 remove() 平均 O(1)，但 getRandom() 是 O(n)（不支持随机访问）。
• 结合使用：才能让所有操作都达到 O(1)。

3. insert() 方法详解

1. 检查元素是否已存在：通过字典快速查找。如果存在，返回 false。
2. 添加到数组末尾：这是 O(1) 操作。
3. 更新索引映射：在字典中记录元素到索引的映射。
4. 返回 true：插入成功。

时间复杂度是 O(1)。

4. remove() 方法详解

这是最关键的删除操作，需要巧妙地处理：

1. 检查元素是否存在：通过字典查找。如果不存在，返回 false。
2. 获取被删除元素的索引：从字典中获取。
3. 获取最后一个元素：获取数组的最后一个元素。
4. 交换位置：将最后一个元素移到被删除元素的位置。避免移动数组中间的元素，保持 O(1)。
5. 更新索引映射：更新最后一个元素在字典中的索引映射。
6. 删除最后一个元素：从数组末尾删除，这是 O(1) 操作。
7. 删除字典映射：从字典中删除被删除元素的映射。

5. getRandom() 方法详解

1. 随机选择索引：使用 Int.random(in: 0..<array.count)。
2. 返回对应元素：通过数组的随机访问返回。

时间复杂度是 O(1)。

6. 边界情况处理

• 插入重复元素：检查元素是否已存在。
• 删除不存在的元素：检查元素是否存在。
• 删除最后一个元素：逻辑仍然正确，因为 lastElement 就是被删除的元素本身。

7. 为什么删除操作是 O(1)？

不是直接删除数组中间的元素，而是将最后一个元素移到被删除元素的位置，然后删除最后一个元素。避免了移动数组中间的元素（O(n) 操作）。

示例测试及结果

示例 1：基本操作

let randomizedSet = RandomizedSet()
print("insert(1): \(randomizedSet.insert(1))") // true
print("insert(2): \(randomizedSet.insert(2))") // true
print("insert(3): \(randomizedSet.insert(3))") // true
print("getRandom(): \(randomizedSet.getRandom())") // 随机返回 1、2 或 3
print("remove(2): \(randomizedSet.remove(2))") // true
print("remove(2): \(randomizedSet.remove(2))") // false（已删除）
print("getRandom(): \(randomizedSet.getRandom())") // 随机返回 1 或 3

示例 2：题目示例

let randomizedSet = RandomizedSet()
print("insert(1): \(randomizedSet.insert(1))") // true
print("remove(2): \(randomizedSet.remove(2))") // false
print("insert(2): \(randomizedSet.insert(2))") // true
print("getRandom(): \(randomizedSet.getRandom())") // 1 或 2
print("remove(1): \(randomizedSet.remove(1))") // true
print("insert(2): \(randomizedSet.insert(2))") // false
print("getRandom(): \(randomizedSet.getRandom())") // 2

示例 3：大量操作测试

let randomizedSet = RandomizedSet()
// 插入 1000 个元素
for i in 0..<1000 {
    _ = randomizedSet.insert(i)
}
print("插入 1000 个元素后，getRandom(): \(randomizedSet.getRandom())")
// 删除前 500 个元素
for i in 0..<500 {
    _ = randomizedSet.remove(i)
}
print("删除 500 个元素后，getRandom(): \(randomizedSet.getRandom())")

时间复杂度

操作	时间复杂度	说明
init()	O(1)	初始化空数组和字典
insert(_ val: Int)	O(1) 平均	数组 append() 是 O(1)，字典插入平均 O(1)
remove(_ val: Int)	O(1) 平均	字典查找平均 O(1)，数组操作是 O(1)
getRandom()	O(1)	数组随机访问是 O(1)

所有操作的平均时间复杂度都是 O(1)。

空间复杂度

• array：存储所有元素，最多存储 n 个元素，O(n)
• dict：存储元素到索引的映射，最多存储 n 个键值对，O(n)

总空间复杂度：O(n)

实际应用场景

这种数据结构设计在实际开发中应用非常广泛：

场景一：抽奖系统

需要从参与者中随机选择一个获奖者，需快速添加和移除参与者。

场景二：随机推荐系统

从候选列表中随机推荐内容，需动态添加和移除候选内容。

场景三：游戏中的随机事件

从事件池中随机触发事件，需动态注册和注销事件。

场景四：负载均衡

从服务器列表中随机选择一个服务器，需动态添加和移除服务器。

总结

这道题涉及重要的设计思想：

1. 数据结构的选择：数组支持 O(1) 随机访问，字典支持 O(1) 查找，两者结合使用能达到最优性能。
2. 时间复杂度优化：通过巧妙的设计，让所有操作都达到 O(1) 的平均时间复杂度。删除操作的关键在于将最后一个元素移到被删除元素的位置。
3. 空间复杂度权衡：虽然使用了两个数据结构，但这是必要的权衡。
4. 实际应用：如抽奖系统、推荐系统、游戏事件系统、负载均衡等。