LeetCode 380：O(1) 时间插入删除和获取随机元素 | 哈希表与数组的结合

LeetCode 380O(1) 时间插入删除和获取随机元素 | 哈希表与数组的结合引言O(1) 时间插入删除和获取随机元素Insert Delete GetRandom O(1)是 LeetCode 第 380 题难度为 Medium。题目要求设计一个数据结构支持在平均 O(1) 时间内完成插入元素、删除元素和随机获取一个元素三种操作。这道题综合运用了哈希表和数组两种数据结构展示了如何通过组合不同数据结构来满足复杂的功能和性能需求。这道题的关键挑战在于如何在 O(1) 时间内同时完成插入、删除和随机访问。哈希表可以提供 O(1) 的插入、删除和查找但无法支持高效的随机访问数组可以支持 O(1) 的随机访问但删除操作需要 O(n) 时间。通过将两者结合我们可以实现所有操作都在 O(1) 时间内完成。问题分析题目描述设计一个数据结构支持以下操作insert(val)如果元素 val 不存在插入并返回 true如果已存在则返回 false。remove(val)如果元素 val 存在删除并返回 true如果不存在则返回 false。getRandom()随机返回现有元素之一每个元素被返回的概率应该相同。例如执行 insert(1)、insert(2)、insert(3) 后getRandom() 应该以相等概率返回 1、2 或 3。执行 remove(2) 后集合变为 [1, 3]getRandom() 应该以相等概率返回 1 或 3。问题特点这道题的挑战在于同时满足三种操作的时间复杂度要求。插入需要 O(1)这可以用哈希表轻松实现。删除需要 O(1)这也可以用哈希表实现通过查找和删除。但随机获取需要 O(1)这需要数组支持随机访问。关键问题是如何处理删除操作。在数组中删除元素通常需要移动后续元素时间复杂度为 O(n)。我们的解决方案是使用交换删除技巧将待删除元素与数组最后一个元素交换然后删除最后一个元素。这样可以将删除操作的时间复杂度降低到 O(1)。数据结构设计我们使用两个数据结构数组 nums存储所有元素支持 O(1) 的随机访问。哈希表 valToIndex存储元素到数组索引的映射支持 O(1) 的查找。插入时将元素添加到数组末尾并在哈希表中记录其索引。删除时通过哈希表查找元素的索引将该元素与数组末尾元素交换然后删除末尾元素并更新哈希表。完整代码实现Python 实现import random class RandomizedSet: def __init__(self): self.nums [] self.valToIndex {} def insert(self, val: int) - bool: if val in self.valToIndex: return False self.valToIndex[val] len(self.nums) self.nums.append(val) return True def remove(self, val: int) - bool: if val not in self.valToIndex: return False index self.valToIndex[val] last_val self.nums[-1] self.nums[index] last_val self.valToIndex[last_val] index self.nums.pop() del self.valToIndex[val] return True def getRandom(self) - int: return random.choice(self.nums)Java 实现import java.util.*; class RandomizedSet { private ListInteger nums; private MapInteger, Integer valToIndex; private Random random; public RandomizedSet() { nums new ArrayList(); valToIndex new HashMap(); random new Random(); } public boolean insert(int val) { if (valToIndex.containsKey(val)) { return false; } valToIndex.put(val, nums.size()); nums.add(val); return true; } public boolean remove(int val) { if (!valToIndex.containsKey(val)) { return false; } int index valToIndex.get(val); int lastVal nums.get(nums.size() - 1); nums.set(index, lastVal); valToIndex.put(lastVal, index); nums.remove(nums.size() - 1); valToIndex.remove(val); return true; } public int getRandom() { return nums.get(random.nextInt(nums.size())); } }算法详解插入操作插入操作首先检查元素是否已存在。如果存在返回 false。如果不存在在哈希表中记录元素及其索引在数组末尾的位置然后将元素添加到数组末尾。def insert(self, val: int) - bool: if val in self.valToIndex: return False self.valToIndex[val] len(self.nums) self.nums.append(val) return True删除操作删除操作是整个设计的核心。步骤如下检查元素是否存在如果不存在返回 false。获取待删除元素的索引。获取数组最后一个元素的值。将最后一个元素移到待删除元素的位置。更新哈希表中最后一个元素的索引映射。删除数组最后一个元素。删除哈希表中待删除元素的映射。def remove(self, val: int) - bool: if val not in self.valToIndex: return False index self.valToIndex[val] last_val self.nums[-1] self.nums[index] last_val self.valToIndex[last_val] index self.nums.pop() del self.valToIndex[val] return True这种交换删除的技巧确保了删除操作的时间复杂度为 O(1)而不需要移动大量元素。随机获取操作随机获取操作使用 Python 的 random.choice 或 Java 的 Random.nextInt 来生成随机索引然后返回对应元素。def getRandom(self) - int: return random.choice(self.nums)为什么需要哈希表哈希表在这里的作用是提供 O(1) 的元素到索引的映射。在删除操作中我们需要知道待删除元素在数组中的位置以便进行交换。如果不使用哈希表查找元素的索引需要 O(n) 时间。使用哈希表可以将这个查找操作降低到 O(1)。哈希表和数组的结合使用是解决这个问题或类似问题的标准技巧。数组提供 O(1) 的随机访问哈希表提供 O(1) 的键值查找两者结合可以满足所有操作的时间复杂度要求。复杂度分析时间复杂度所有三种操作的时间复杂度都是 O(1)insert哈希表查找和插入是 O(1)数组添加是 O(1)。remove哈希表查找是 O(1)数组操作是 O(1)。getRandom数组随机访问是 O(1)。空间复杂度空间复杂度为 O(n)其中 n 是集合中的元素数量。数组和哈希表都需要存储 n 个元素。边界情况处理空集合当集合为空时getRandom 操作不应该被调用题目假设所有操作都是合法的。如果需要处理可以返回 -1 或抛出异常。单个元素当集合只有一个元素时插入、删除和 getRandom 都应该正确工作。删除后集合为空。重复插入和删除连续多次插入相同元素只有第一次会成功。连续多次删除相同元素只有第一次会成功第二次会返回 false。这符合题目要求。插入后删除相同元素insert(val) 后 remove(val) 应该成功。删除后集合状态应该与插入前相同假设之前集合中只有 val。变种问题O(1) 时间插入删除和获取随机元素允许重复如果允许集合包含重复元素即多重集合需要修改设计。可以使用数组加哈希表值到索引列表的映射来实现class RandomizedCollection: def __init__(self): self.nums [] self.valToIndices defaultdict(set()) def insert(self, val: int) - bool: self.valToIndices[val].add(len(self.nums)) self.nums.append(val) return len(self.valToIndices[val]) 1O(1) 时间获取随机不同元素如果要求 getRandom 返回一个不存在于当前集合中的随机元素即从所有可能的元素中随机选择但排除已在集合中的这个问题会更加复杂。测试用例def test_randomized_set(): rs RandomizedSet() assert rs.insert(1) True assert rs.insert(2) True assert rs.insert(3) True assert rs.insert(2) False assert rs.getRandom() in [1, 2, 3] assert rs.remove(2) True assert rs.remove(2) False assert rs.getRandom() in [1, 3] assert rs.insert(4) True result [rs.getRandom() for _ in range(100)] assert 4 in result print(所有测试用例通过)实际应用场景O(1) 插入删除和随机获取在现实中有很多应用。在洗牌算法中需要随机打乱一副牌可以使用类似的数据结构。在采样问题中需要从数据流中随机采样可以使用蓄水池抽样算法但如果有删除需求就需要类似的设计。在游戏开发中如果需要实现一个随机掉落系统每个物品有独立的掉落概率可以使用加权随机选择算法。而如果需要支持动态添加和删除物品并保持随机选择的均匀性类似的数据结构就能派上用场。总结O(1) 时间插入删除和获取随机元素问题展示了如何通过组合哈希表和数组来满足复杂的功能和性能需求。哈希表提供 O(1) 的键值查找数组提供 O(1) 的随机访问两者结合是解决这类问题的标准技巧。交换删除的技巧是这个解决方案的点睛之笔它将数组删除操作的时间复杂度从 O(n) 降低到 O(1)。这种通过改变数据结构组织方式来优化操作效率的思想在算法设计中非常重要。希望通过本文的讲解读者能够掌握这种组合数据结构的思路并将其应用到更多类似问题的解决中。