leetcode:380. 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 。

提示：

• -231 <= val <= 231 - 1
• 最多调用 insert、remove 和 getRandom 函数 2 * 105 次
• 在调用 getRandom 方法时，数据结构中 至少存在一个 元素。

步骤1：问题定义及输入输出条件

问题性质：
该题目要求实现一个数据结构RandomizedSet，可以高效地执行以下操作：

1. 插入：如果元素不存在，将其插入集合。
2. 删除：如果元素存在，将其从集合中删除。
3. 随机获取元素：随机返回集合中的一个元素，且每个元素有相同的概率被返回。

输入输出条件：

• insert(int val)：如果val不存在于集合中，则插入该元素并返回true；如果存在，则返回false。
• remove(int val)：如果val存在于集合中，删除该元素并返回true；如果不存在，返回false。
• getRandom()：随机返回集合中的一个元素，要求每个元素的返回概率相同。

限制与边界条件：

• 数据范围：val 取值范围为 [-2^31, 2^31-1]，函数调用次数最多为 2*10^5。
• 调用 getRandom() 时，保证集合中至少存在一个元素。

边界条件：

1. 空集合：remove时如果元素不在集合中，或者对空集合调用getRandom可能会产生边界错误。
2. 频繁操作：高频调用insert、remove和getRandom，每次操作的平均时间复杂度需为O(1)。

步骤2：解题思路与算法设计

目标：

• 插入、删除和获取随机元素的平均时间复杂度为O(1)。

算法设计：

1. 数据结构选择：

   • 哈希表 (unordered_map) + 动态数组 (vector)：
     • 使用一个哈希表 map<int, int> 来存储元素到其在数组中的位置的映射。
     • 使用一个动态数组 vector<int> 存储元素值。
     • 这样在插入和删除时，都可以保持O(1)的复杂度，并且可以利用数组支持O(1)时间复杂度的随机访问。

2. 操作细节：

   • insert(val)：
     • 检查val是否存在于哈希表中。如果不存在，插入到数组末尾，并更新哈希表，时间复杂度为O(1)。
   • remove(val)：
     • 通过哈希表定位val在数组中的位置。为了保持删除操作的O(1)，我们将待删除的元素与数组末尾元素交换，然后删除末尾元素，并更新哈希表。
   • getRandom()：
     • 直接从数组中随机获取一个元素，时间复杂度为O(1)。

时间复杂度分析：

• insert: 哈希表插入是O(1)，动态数组末尾插入是O(1)。
• remove: 哈希表删除是O(1)，动态数组末尾删除是O(1)。
• getRandom: 直接从数组中随机访问，时间复杂度为O(1)。

步骤3：代码实现

代码注释：

1. insert(int val)：当val不在哈希表中时，将其加入到数组的末尾，并记录其在哈希表中的索引。
2. remove(int val)：先从哈希表中获取待删除元素的位置，将其与数组的最后一个元素交换，再删除最后一个元素，确保删除操作的时间复杂度为O(1)。
3. getRandom()：利用数组的随机访问特性，直接生成一个随机索引返回对应的元素。

步骤4：算法优化和启发

通过该问题，我们可以看到如何将多种数据结构结合起来以提升算法效率。哈希表可以实现快速查找，动态数组可以实现高效的随机访问和插入。通过交换和删除末尾元素，可以确保删除操作的O(1)复杂度。

优化启发：

• 空间效率：虽然结合哈希表和数组可以实现高效的时间复杂度，但需要占用较多的空间。如果数据量非常大，需要权衡时间和空间的平衡。
• 算法设计思路：此问题展示了如何使用简单的数据结构组合来解决复杂问题，在实际应用中，通过合理的数据结构选择可以极大地提升效率。

步骤5：实际应用场景

该算法可以用于许多需要高效集合操作的场景，比如：

• 在线游戏服务器：当需要随机选择在线玩家进行匹配时，可以使用该结构存储在线玩家列表并随机选择。
• 负载均衡：在负载均衡系统中，随机选择服务器进行请求分发，可以通过类似的数据结构实现高效选择和删除。

实际应用示例：负载均衡中的随机服务器选择

在大规模服务器集群中，通常需要从可用的服务器列表中随机选择一台服务器进行任务分发。如果某些服务器挂掉，还需要将其从列表中移除。使用类似RandomizedSet的结构可以高效地管理服务器列表，并快速随机选取可用服务器进行负载均衡。

通过哈希表来快速定位服务器，结合数组来实现随机选择，使得服务器的添加、移除和随机选择都能够在常数时间内完成，提升系统的响应速度和稳定性。