Swift算法
LeetCode 380: O(1) 时间插入、删除和获取随机元素
本文介绍如何使用 Swift 实现 LeetCode 380 题，设计一个支持 O(1) 时间复杂度的插入、删除和随机获取元素的数据结构。核心方案结合使用数组和哈希表：数组用于 O(1) 随机访问，哈希表用于 O(1) 查找元素索引。删除操作通过将待删元素与数组末尾元素交换来实现 O(1) 复杂度。该模式适用于抽奖系统、负载均衡等需要高效随机操作的场景。
本文介绍如何使用 Swift 实现 LeetCode 380 题，设计一个支持 O(1) 时间复杂度的插入、删除和随机获取元素的数据结构。核心方案结合使用数组和哈希表：数组用于 O(1) 随机访问，哈希表用于 O(1) 查找元素索引。删除操作通过将待删元素与数组末尾元素交换来实现 O(1) 复杂度。该模式适用于抽奖系统、负载均衡等需要高效随机操作的场景。
这道题要求设计一个数据结构，能够支持 O(1) 时间复杂度的插入、删除和随机获取操作。如果只用数组，删除操作是 O(n)；如果只用 Set，随机获取操作是 O(n)。我们需要巧妙地结合数组和字典，才能让所有操作都达到 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^31 <= val <= 2^31 - 1insert、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]
}
}
这道题的关键在于选择合适的数据结构来支持 O(1) 的操作：
private var array: [Int]
private var dict: [Int: Int]
我们使用了两个数据结构：
array：一个数组，用来存储所有元素。数组支持 O(1) 的随机访问，这对于 getRandom() 操作非常重要dict：一个字典，用来存储元素到索引的映射。字典支持 O(1) 的查找和删除，这对于 insert() 和 remove() 操作非常重要如果只用数组：
insert()：O(1)（添加到末尾）remove()：O(n)（需要查找元素，然后移动后面的元素）getRandom()：O(1)（随机访问）如果只用 Set：
insert()：O(1) 平均remove()：O(1) 平均getRandom()：O(n)（Set 不支持随机访问，需要转换为数组）所以我们需要结合数组和字典，才能让所有操作都达到 O(1)。
func insert(_ val: Int) -> Bool {
// 如果元素已存在，返回 false
if dict[val] != nil {
return false
}
// 将元素添加到数组末尾
array.append(val)
// 记录元素在数组中的索引
dict[val] = array.count - 1
return true
}
insert() 方法的逻辑是：
false时间复杂度是 O(1)，因为数组的 append() 和字典的插入都是 O(1) 操作。
这是最关键的删除操作，需要巧妙地处理：
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() 方法的逻辑是：
false这个技巧的关键在于：我们不是直接删除数组中间的元素（这会导致 O(n) 的移动操作），而是将最后一个元素移到被删除元素的位置，然后删除最后一个元素。这样就能保证 O(1) 的时间复杂度。
func getRandom() -> Int {
// 随机选择一个索引
let randomIndex = Int.random(in: 0..<array.count)
return array[randomIndex]
}
getRandom() 方法的逻辑很简单：
Int.random(in: 0..<array.count) 随机选择一个有效的索引时间复杂度是 O(1)，因为数组支持 O(1) 的随机访问。
代码中处理了几个重要的边界情况：
falsefalselastElement 就是被删除的元素本身，但逻辑仍然正确，因为我们会先更新索引映射，然后删除删除操作的关键在于我们不是直接删除数组中间的元素，而是：
这样做的优势：
所以整个删除操作的时间复杂度是 O(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
执行过程分析：
array = [], dict = [:]insert(1)：
array = [1]dict = [1: 0]trueinsert(2)：
array = [1, 2]dict = [1: 0, 2: 1]trueinsert(3)：
array = [1, 2, 3]dict = [1: 0, 2: 1, 3: 2]truegetRandom()：随机返回 1、2 或 3remove(2)：
index = 1lastElement = 3array[1] = 3（将 3 移到位置 1）dict[3] = 1（更新 3 的索引）array.removeLast()（删除最后一个元素）dict.removeValue(forKey: 2)（删除 2 的映射）array = [1, 3], dict = [1: 0, 3: 1]trueremove(2)：元素不存在，返回 falsegetRandom()：随机返回 1 或 3let 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
执行过程分析：
insert(1)：array = [1], dict = [1: 0], 返回 trueremove(2)：元素不存在，返回 falseinsert(2)：array = [1, 2], dict = [1: 0, 2: 1], 返回 truegetRandom()：随机返回 1 或 2remove(1)：
index = 0lastElement = 2array[0] = 2dict[2] = 0array.removeLast()dict.removeValue(forKey: 1)array = [2], dict = [2: 0]trueinsert(2)：元素已存在，返回 falsegetRandom()：返回 2（唯一元素）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) 次")
}
这个测试展示了系统在处理大量操作时的正确性和随机性。
让我们分析一下每个操作的时间复杂度：
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
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)，完全满足题目要求。
对于题目约束（最多调用 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()
}
}
这种场景下，我们需要能够动态地添加和移除服务器，并且能够随机选择服务器进行负载均衡。
这道题虽然看起来简单，但实际上涉及了很多重要的设计思想：
关键点总结：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online