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

提示：

• -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 - 1]
        // 将最后一个元素移到被删除元素的位置
        array[index] = lastElement
        // 更新最后一个元素的索引映射
        dict[lastElement] = index
        // 删除数组最后一个元素（O(1) 操作）
        array.removeLast()
        // 删除字典中的映射
        dict.removeValue(forKey: val)
        return true
    }

    /// 随机获取元素
    func getRandom() -> Int {
        // 随机选择一个索引
        let randomIndex = Int.random(in: 0..<array.count)
        return array[randomIndex]
    }
}

题解代码分析

1. 数据结构的选择

这道题的关键在于选择合适的数据结构来支持 O(1) 的操作：

private var array: [Int]
private var dict: [Int: Int]

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

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

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

如果只用数组：

• insert()：O(1)（添加到末尾）
• remove()：O(n)（需要查找元素，然后移动后面的元素）
• getRandom()：O(1)（随机访问）

如果只用 Set：

• insert()：O(1) 平均
• remove()：O(1) 平均
• getRandom()：O(n)（Set 不支持随机访问，需要转换为数组）

所以我们需要结合数组和字典，才能让所有操作都达到 O(1)。

3. insert() 方法详解

func insert(_ val: Int) -> Bool {
    // 如果元素已存在，返回 false
    if dict[val] != nil {
        return false
    }
    // 将元素添加到数组末尾
    array.append(val)
    // 记录元素在数组中的索引
    dict[val] = array.count - 1
    return true
}

insert() 方法的逻辑是：

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

时间复杂度是 O(1)，因为数组的 append() 和字典的插入都是 O(1) 操作。

4. remove() 方法详解

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

func remove(_ val: Int) -> Bool {
    // 如果元素不存在，返回 false
    guard let index = dict[val] else {
        return false
    }
    // 获取数组最后一个元素
    let lastElement = array[array.count - 1]
    // 将最后一个元素移到被删除元素的位置
    array[index] = lastElement
    // 更新最后一个元素的索引映射
    dict[lastElement] = index
    // 删除数组最后一个元素（O(1) 操作）
    array.removeLast()
    // 删除字典中的映射
    dict.removeValue(forKey: val)
    return true
}

remove() 方法的逻辑是：

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

这个技巧的关键在于：我们不是直接删除数组中间的元素（这会导致 O(n) 的移动操作），而是将最后一个元素移到被删除元素的位置，然后删除最后一个元素。这样就能保证 O(1) 的时间复杂度。

5. getRandom() 方法详解

func getRandom() -> Int {
    // 随机选择一个索引
    let randomIndex = Int.random(in: 0..<array.count)
    return array[randomIndex]
}

getRandom() 方法的逻辑很简单：

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

时间复杂度是 O(1)，因为数组支持 O(1) 的随机访问。

6. 边界情况处理

代码中处理了几个重要的边界情况：

1. 插入重复元素：检查元素是否已存在，如果存在就返回 false
2. 删除不存在的元素：检查元素是否存在，如果不存在就返回 false
3. 删除最后一个元素：当删除最后一个元素时，lastElement 就是被删除的元素本身，但逻辑仍然正确，因为我们会先更新索引映射，然后删除

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

删除操作的关键在于我们不是直接删除数组中间的元素，而是：

1. 将最后一个元素移到被删除元素的位置
2. 删除最后一个元素

这样做的优势：

• 避免了移动数组中间的元素（O(n) 操作）
• 只需要更新一个元素的索引映射
• 删除数组最后一个元素是 O(1) 操作

所以整个删除操作的时间复杂度是 O(1)。

示例测试及结果

让我们用几个例子来测试一下这个解决方案：

示例 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

执行过程分析：

1. 初始化：array = [], dict = [:]
2. insert(1)：
   • array = [1]
   • dict = [1: 0]
   • 返回 true
3. insert(2)：
   • array = [1, 2]
   • dict = [1: 0, 2: 1]
   • 返回 true
4. insert(3)：
   • array = [1, 2, 3]
   • dict = [1: 0, 2: 1, 3: 2]
   • 返回 true
5. getRandom()：随机返回 1、2 或 3
6. remove(2)：
   • 找到 index = 1
   • lastElement = 3
   • array[1] = 3（将 3 移到位置 1）
   • dict[3] = 1（更新 3 的索引）
   • array.removeLast()（删除最后一个元素）
   • dict.removeValue(forKey: 2)（删除 2 的映射）
   • array = [1, 3], dict = [1: 0, 3: 1]
   • 返回 true
7. remove(2)：元素不存在，返回 false
8. 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

执行过程分析：

1. insert(1)：array = [1], dict = [1: 0], 返回 true
2. remove(2)：元素不存在，返回 false
3. insert(2)：array = [1, 2], dict = [1: 0, 2: 1], 返回 true
4. getRandom()：随机返回 1 或 2
5. remove(1)：
   • index = 0
   • lastElement = 2
   • array[0] = 2
   • dict[2] = 0
   • array.removeLast()
   • dict.removeValue(forKey: 1)
   • array = [2], dict = [2: 0]
   • 返回 true
6. insert(2)：元素已存在，返回 false
7. 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())")
// 统计随机获取的结果分布
var count: [Int: Int] = [:]
for _ in 0..<10000 {
    let random = randomizedSet.getRandom()
    count[random, default: 0] += 1
}
print("随机获取 10000 次的结果分布（前 10 个）:")
let sorted = count.sorted { $0.value > $1.value }.prefix(10)
for (key, value) in sorted {
    print("\(key): \(value) 次")
}

这个测试展示了系统在处理大量操作时的正确性和随机性。

时间复杂度

让我们分析一下每个操作的时间复杂度：

总体时间复杂度：

所有操作的平均时间复杂度都是 O(1)，完全满足题目要求。

对于题目约束（最多调用 2 * 10^5 次），这个时间复杂度是完全可接受的。

空间复杂度

空间复杂度分析：

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

总空间复杂度：O(n)

其中 n 是集合中元素的数量。虽然我们使用了两个数据结构，但它们存储的是相同数量的数据，所以空间复杂度是 O(n)，这是必要的，因为我们需要同时支持 O(1) 的查找和随机访问。

实际应用场景

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

场景一：抽奖系统

在抽奖系统中，我们需要从参与者中随机选择一个获奖者：

class LotterySystem {
    private var participants: RandomizedSet
    
    init() {
        self.participants = RandomizedSet()
    }
    
    func addParticipant(_ id: Int) {
        participants.insert(id)
    }
    
    func removeParticipant(_ id: Int) {
        participants.remove(id)
    }
    
    func drawWinner() -> Int? {
        guard participants.array.count > 0 else {
            return nil
        }
        return participants.getRandom()
    }
}

这种场景下，我们需要能够快速添加和移除参与者，并且能够公平地随机选择获奖者。

场景二：随机推荐系统

在推荐系统中，我们需要从候选列表中随机推荐内容：

class RecommendationSystem {
    private var candidates: RandomizedSet
    
    init() {
        self.candidates = RandomizedSet()
    }
    
    func addCandidate(_ id: Int) {
        candidates.insert(id)
    }
    
    func removeCandidate(_ id: Int) {
        candidates.remove(id)
    }
    
    func getRandomRecommendation() -> Int {
        return candidates.getRandom()
    }
}

这种场景下，我们需要能够动态地添加和移除候选内容，并且能够随机推荐。

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

在游戏中，我们需要从事件池中随机触发事件：

class EventSystem {
    private var events: RandomizedSet
    
    init() {
        self.events = RandomizedSet()
    }
    
    func registerEvent(_ eventId: Int) {
        events.insert(eventId)
    }
    
    func unregisterEvent(_ eventId: Int) {
        events.remove(eventId)
    }
    
    func triggerRandomEvent() -> Int {
        return events.getRandom()
    }
}

这种场景下，我们需要能够动态地注册和注销事件，并且能够随机触发事件。

场景四：负载均衡

在负载均衡中，我们需要从服务器列表中随机选择一个服务器：

class LoadBalancer {
    private var servers: RandomizedSet
    
    init() {
        self.servers = RandomizedSet()
    }
    
    func addServer(_ serverId: Int) {
        servers.insert(serverId)
    }
    
    func removeServer(_ serverId: Int) {
        servers.remove(serverId)
    }
    
    func selectServer() -> Int {
        return servers.getRandom()
    }
}

这种场景下，我们需要能够动态地添加和移除服务器，并且能够随机选择服务器进行负载均衡。

总结

这道题虽然看起来简单，但实际上涉及了很多重要的设计思想：

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

关键点总结：

• 使用数组存储元素，支持 O(1) 随机访问
• 使用字典存储元素到索引的映射，支持 O(1) 查找和删除
• 删除时，将最后一个元素移到被删除元素的位置，保证 O(1) 删除
• 所有操作的平均时间复杂度都是 O(1)