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

摘要

这道题其实挺有意思的，它要求我们设计一个数据结构，能够支持 O(1) 时间复杂度的插入、删除和随机获取操作。听起来简单，但实际做起来还是需要一些技巧的。如果只用数组，删除操作是 O(n)；如果只用 Set，随机获取操作是 O(n)。我们需要巧妙地结合数组和字典，才能让所有操作都达到 O(1) 的时间复杂度。

这道题的核心在于如何高效地管理元素的存储和索引，既要能快速插入和删除，又要能快速随机获取。今天我们就用 Swift 来搞定这道题，顺便聊聊这种设计模式在实际开发中的应用场景。

描述

题目要求是这样的：实现RandomizedSet类，需要支持以下操作：

1. RandomizedSet()：初始化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 表示 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 - 1
• 最多调用insert、remove和getRandom函数2 * 10^5次
• 在调用getRandom方法时，数据结构中至少存在一个元素

这道题的核心思路是什么呢？我们需要同时使用数组和字典：数组用来存储元素，支持 O(1) 的随机访问；字典用来存储元素到索引的映射，支持 O(1) 的查找和删除。删除时，我们将最后一个元素移到被删除元素的位置，然后删除最后一个元素，这样就能保证 O(1) 的删除操作。

题解答案

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

classRandomizedSet{// 数组：存储所有元素，支持 O(1) 随机访问privatevararray:[Int]// 字典：存储元素到索引的映射，支持 O(1) 查找和删除privatevardict:[Int:Int]init(){self.array=[]self.dict=[:]}/// 插入元素funcinsert(_val:Int)->Bool{// 如果元素已存在，返回 falseifdict[val]!=nil{returnfalse}// 将元素添加到数组末尾array.append(val)// 记录元素在数组中的索引dict[val]=array.count-1returntrue}/// 删除元素funcremove(_val:Int)->Bool{// 如果元素不存在，返回 falseguardletindex=dict[val]else{returnfalse}// 获取数组最后一个元素letlastElement=array[array.count-1]// 将最后一个元素移到被删除元素的位置array[index]=lastElement// 更新最后一个元素的索引映射dict[lastElement]=index// 删除数组最后一个元素（O(1) 操作）array.removeLast()// 删除字典中的映射dict.removeValue(forKey:val)returntrue}/// 随机获取元素funcgetRandom()->Int{// 随机选择一个索引letrandomIndex=Int.random(in:0..<array.count)returnarray[randomIndex]}}

题解代码分析

让我们一步步分析这个解决方案：

1. 数据结构的选择

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

privatevararray:[Int]privatevardict:[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() 方法详解

funcinsert(_val:Int)->Bool{// 如果元素已存在，返回 falseifdict[val]!=nil{returnfalse}// 将元素添加到数组末尾array.append(val)// 记录元素在数组中的索引dict[val]=array.count-1returntrue}

insert()方法的逻辑是：

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

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

4. remove() 方法详解

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

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

remove()方法的逻辑是：

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

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

5. getRandom() 方法详解

funcgetRandom()->Int{// 随机选择一个索引letrandomIndex=Int.random(in:0..<array.count)returnarray[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：基本操作

letrandomizedSet=RandomizedSet()print("insert(1):\(randomizedSet.insert(1))")// trueprint("insert(2):\(randomizedSet.insert(2))")// trueprint("insert(3):\(randomizedSet.insert(3))")// trueprint("getRandom():\(randomizedSet.getRandom())")// 随机返回 1、2 或 3print("remove(2):\(randomizedSet.remove(2))")// trueprint("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：题目示例

letrandomizedSet=RandomizedSet()print("insert(1):\(randomizedSet.insert(1))")// trueprint("remove(2):\(randomizedSet.remove(2))")// falseprint("insert(2):\(randomizedSet.insert(2))")// trueprint("getRandom():\(randomizedSet.getRandom())")// 1 或 2print("remove(1):\(randomizedSet.remove(1))")// trueprint("insert(2):\(randomizedSet.insert(2))")// falseprint("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：大量操作测试

letrandomizedSet=RandomizedSet()// 插入 1000 个元素foriin0..<1000{_=randomizedSet.insert(i)}print("插入 1000 个元素后，getRandom():\(randomizedSet.getRandom())")// 删除前 500 个元素foriin0..<500{_=randomizedSet.remove(i)}print("删除 500 个元素后，getRandom():\(randomizedSet.getRandom())")// 统计随机获取的结果分布varcount:[Int:Int]=[:]for_in0..<10000{letrandom=randomizedSet.getRandom()count[random,default:0]+=1}print("随机获取 10000 次的结果分布（前10个）:")letsorted=count.sorted{$0.value>$1.value}.prefix(10)for(key,value)insorted{print("\(key):\(value)次")}

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

时间复杂度

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

总体时间复杂度：

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

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

空间复杂度

空间复杂度分析：

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

总空间复杂度：O(n)

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

实际应用场景

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

场景一：抽奖系统

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

classLotterySystem{privatevarparticipants:RandomizedSetinit(){self.participants=RandomizedSet()}funcaddParticipant(_id:Int){participants.insert(id)}funcremoveParticipant(_id:Int){participants.remove(id)}funcdrawWinner()->Int?{guardparticipants.array.count>0else{returnnil}returnparticipants.getRandom()}}

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

场景二：随机推荐系统

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

classRecommendationSystem{privatevarcandidates:RandomizedSetinit(){self.candidates=RandomizedSet()}funcaddCandidate(_id:Int){candidates.insert(id)}funcremoveCandidate(_id:Int){candidates.remove(id)}funcgetRandomRecommendation()->Int{returncandidates.getRandom()}}

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

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

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

classEventSystem{privatevarevents:RandomizedSetinit(){self.events=RandomizedSet()}funcregisterEvent(_eventId:Int){events.insert(eventId)}funcunregisterEvent(_eventId:Int){events.remove(eventId)}functriggerRandomEvent()->Int{returnevents.getRandom()}}

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

场景四：负载均衡

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

classLoadBalancer{privatevarservers:RandomizedSetinit(){self.servers=RandomizedSet()}funcaddServer(_serverId:Int){servers.insert(serverId)}funcremoveServer(_serverId:Int){servers.remove(serverId)}funcselectServer()->Int{returnservers.getRandom()}}

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

总结

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

1. 数据结构的选择：选择合适的数据结构来支持不同的操作。数组支持 O(1) 随机访问，字典支持 O(1) 查找，两者结合使用能达到最优性能。

2. 时间复杂度优化：通过巧妙的设计，让所有操作都达到 O(1) 的平均时间复杂度。删除操作的关键在于将最后一个元素移到被删除元素的位置，避免移动数组中间的元素。

3. 空间复杂度权衡：虽然使用了两个数据结构，但这是必要的权衡，因为我们需要同时支持 O(1) 的查找和随机访问。

4. 实际应用：这种设计模式在实际开发中应用广泛，如抽奖系统、推荐系统、游戏事件系统、负载均衡等。

关键点总结：

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