企业官网建设流程全解析

东莞seo建站视频,wordpress关闭主题,免费网络推广网站,wordpress 放视频文章目录摘要描述题解答案题解代码分析1. 数据结构的选择2. 为什么需要两个数据结构#xff1f;3. insert() 方法详解4. remove() 方法详解5. getRandom() 方法详解6. 边界情况处理7. 为什么删除操作是 O(1)#xff1f;示例测试及结果示例 1#xff1a;基本操作示例 2#…文章目录摘要描述题解答案题解代码分析1. 数据结构的选择2. 为什么需要两个数据结构3. insert() 方法详解4. remove() 方法详解5. getRandom() 方法详解6. 边界情况处理7. 为什么删除操作是 O(1)示例测试及结果示例 1基本操作示例 2题目示例示例 3大量操作测试时间复杂度空间复杂度实际应用场景场景一抽奖系统场景二随机推荐系统场景三游戏中的随机事件场景四负载均衡总结摘要这道题其实挺有意思的它要求我们设计一个数据结构能够支持 O(1) 时间复杂度的插入、删除和随机获取操作。听起来简单但实际做起来还是需要一些技巧的。如果只用数组删除操作是 O(n)如果只用 Set随机获取操作是 O(n)。我们需要巧妙地结合数组和字典才能让所有操作都达到 O(1) 的时间复杂度。这道题的核心在于如何高效地管理元素的存储和索引既要能快速插入和删除又要能快速随机获取。今天我们就用 Swift 来搞定这道题顺便聊聊这种设计模式在实际开发中的应用场景。描述题目要求是这样的实现RandomizedSet类需要支持以下操作RandomizedSet()初始化RandomizedSet对象bool insert(int val)当元素val不存在时向集合中插入该项并返回true否则返回falsebool remove(int val)当元素val存在时从集合中移除该项并返回true否则返回falseint 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{// 如果元素不存在返回 falseguardletindexdict[val]else{returnfalse}// 获取数组最后一个元素letlastElementarray[array.count-1]// 将最后一个元素移到被删除元素的位置array[index]lastElement// 更新最后一个元素的索引映射dict[lastElement]index// 删除数组最后一个元素O(1) 操作array.removeLast()// 删除字典中的映射dict.removeValue(forKey:val)returntrue}/// 随机获取元素funcgetRandom()-Int{// 随机选择一个索引letrandomIndexInt.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)随机访问如果只用 Setinsert()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()方法的逻辑是检查元素是否已存在通过字典快速查找元素是否已存在。如果存在返回false添加到数组末尾将新元素添加到数组末尾这是 O(1) 操作更新索引映射在字典中记录元素到索引的映射这样后续可以快速找到元素的位置返回 true插入成功时间复杂度是 O(1)因为数组的append()和字典的插入都是 O(1) 操作。4. remove() 方法详解这是最关键的删除操作需要巧妙地处理funcremove(_val:Int)-Bool{// 如果元素不存在返回 falseguardletindexdict[val]else{returnfalse}// 获取数组最后一个元素letlastElementarray[array.count-1]// 将最后一个元素移到被删除元素的位置array[index]lastElement// 更新最后一个元素的索引映射dict[lastElement]index// 删除数组最后一个元素O(1) 操作array.removeLast()// 删除字典中的映射dict.removeValue(forKey:val)returntrue}remove()方法的逻辑是检查元素是否存在通过字典快速查找元素是否存在。如果不存在返回false获取被删除元素的索引从字典中获取元素在数组中的索引获取最后一个元素获取数组的最后一个元素交换位置将最后一个元素移到被删除元素的位置。这样做的目的是避免移动数组中间的元素保持 O(1) 的时间复杂度更新索引映射更新最后一个元素在字典中的索引映射删除最后一个元素从数组末尾删除元素这是 O(1) 操作删除字典映射从字典中删除被删除元素的映射返回 true删除成功这个技巧的关键在于我们不是直接删除数组中间的元素这会导致 O(n) 的移动操作而是将最后一个元素移到被删除元素的位置然后删除最后一个元素。这样就能保证 O(1) 的时间复杂度。5. getRandom() 方法详解funcgetRandom()-Int{// 随机选择一个索引letrandomIndexInt.random(in:0..array.count)returnarray[randomIndex]}getRandom()方法的逻辑很简单随机选择索引使用Int.random(in: 0..array.count)随机选择一个有效的索引返回对应元素通过数组的随机访问返回对应位置的元素时间复杂度是 O(1)因为数组支持 O(1) 的随机访问。6. 边界情况处理代码中处理了几个重要的边界情况插入重复元素检查元素是否已存在如果存在就返回false删除不存在的元素检查元素是否存在如果不存在就返回false删除最后一个元素当删除最后一个元素时lastElement就是被删除的元素本身但逻辑仍然正确因为我们会先更新索引映射然后删除7. 为什么删除操作是 O(1)删除操作的关键在于我们不是直接删除数组中间的元素而是将最后一个元素移到被删除元素的位置删除最后一个元素这样做的优势避免了移动数组中间的元素O(n) 操作只需要更新一个元素的索引映射删除数组最后一个元素是 O(1) 操作所以整个删除操作的时间复杂度是 O(1)。示例测试及结果让我们用几个例子来测试一下这个解决方案示例 1基本操作letrandomizedSetRandomizedSet()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执行过程分析初始化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 移到位置 1dict[3] 1更新 3 的索引array.removeLast()删除最后一个元素dict.removeValue(forKey: 2)删除 2 的映射array [1, 3],dict [1: 0, 3: 1]返回trueremove(2)元素不存在返回falsegetRandom()随机返回 1 或 3示例 2题目示例letrandomizedSetRandomizedSet()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执行过程分析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唯一元素示例 3大量操作测试letrandomizedSetRandomizedSet()// 插入 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{letrandomrandomizedSet.getRandom()count[random,default:0]1}print(随机获取 10000 次的结果分布前10个:)letsortedcount.sorted{$0.value$1.value}.prefix(10)for(key,value)insorted{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) 的查找和随机访问。实际应用场景这种数据结构设计在实际开发中应用非常广泛场景一抽奖系统在抽奖系统中我们需要从参与者中随机选择一个获奖者classLotterySystem{privatevarparticipants:RandomizedSetinit(){self.participantsRandomizedSet()}funcaddParticipant(_id:Int){participants.insert(id)}funcremoveParticipant(_id:Int){participants.remove(id)}funcdrawWinner()-Int?{guardparticipants.array.count0else{returnnil}returnparticipants.getRandom()}}这种场景下我们需要能够快速添加和移除参与者并且能够公平地随机选择获奖者。场景二随机推荐系统在推荐系统中我们需要从候选列表中随机推荐内容classRecommendationSystem{privatevarcandidates:RandomizedSetinit(){self.candidatesRandomizedSet()}funcaddCandidate(_id:Int){candidates.insert(id)}funcremoveCandidate(_id:Int){candidates.remove(id)}funcgetRandomRecommendation()-Int{returncandidates.getRandom()}}这种场景下我们需要能够动态地添加和移除候选内容并且能够随机推荐。场景三游戏中的随机事件在游戏中我们需要从事件池中随机触发事件classEventSystem{privatevarevents:RandomizedSetinit(){self.eventsRandomizedSet()}funcregisterEvent(_eventId:Int){events.insert(eventId)}funcunregisterEvent(_eventId:Int){events.remove(eventId)}functriggerRandomEvent()-Int{returnevents.getRandom()}}这种场景下我们需要能够动态地注册和注销事件并且能够随机触发事件。场景四负载均衡在负载均衡中我们需要从服务器列表中随机选择一个服务器classLoadBalancer{privatevarservers:RandomizedSetinit(){self.serversRandomizedSet()}funcaddServer(_serverId:Int){servers.insert(serverId)}funcremoveServer(_serverId:Int){servers.remove(serverId)}funcselectServer()-Int{returnservers.getRandom()}}这种场景下我们需要能够动态地添加和移除服务器并且能够随机选择服务器进行负载均衡。总结这道题虽然看起来简单但实际上涉及了很多重要的设计思想数据结构的选择选择合适的数据结构来支持不同的操作。数组支持 O(1) 随机访问字典支持 O(1) 查找两者结合使用能达到最优性能。时间复杂度优化通过巧妙的设计让所有操作都达到 O(1) 的平均时间复杂度。删除操作的关键在于将最后一个元素移到被删除元素的位置避免移动数组中间的元素。空间复杂度权衡虽然使用了两个数据结构但这是必要的权衡因为我们需要同时支持 O(1) 的查找和随机访问。实际应用这种设计模式在实际开发中应用广泛如抽奖系统、推荐系统、游戏事件系统、负载均衡等。关键点总结使用数组存储元素支持 O(1) 随机访问使用字典存储元素到索引的映射支持 O(1) 查找和删除删除时将最后一个元素移到被删除元素的位置保证 O(1) 删除所有操作的平均时间复杂度都是 O(1)