leetcode
leetcode 351 ~ 400
O(1) 时间插入、删除和获取随机元素 - 允许重复

O(1) 时间插入、删除和获取随机元素 - 允许重复

难度:

标签:

题目描述

RandomizedCollection 是一种包含数字集合(可能是重复的)的数据结构。它应该支持插入和删除特定元素，以及删除随机元素。

实现 RandomizedCollection 类:

  • RandomizedCollection()初始化空的 RandomizedCollection 对象。
  • bool insert(int val) 将一个 val 项插入到集合中，即使该项已经存在。如果该项不存在，则返回 true ，否则返回 false 。
  • bool remove(int val) 如果存在，从集合中移除一个 val 项。如果该项存在，则返回 true ，否则返回 false 。注意，如果 val 在集合中出现多次，我们只删除其中一个。
  • int getRandom() 从当前的多个元素集合中返回一个随机元素。每个元素被返回的概率与集合中包含的相同值的数量 线性相关 。

您必须实现类的函数，使每个函数的 平均 时间复杂度为 O(1) 。

注意：生成测试用例时，只有在 RandomizedCollection 中 至少有一项 时，才会调用 getRandom 。

 

示例 1:

输入
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]
输出
[null, true, false, true, 2, true, 1]

解释
RandomizedCollection collection = new RandomizedCollection();// 初始化一个空的集合。
collection.insert(1);   // 返回 true，因为集合不包含 1。
                        // 将 1 插入到集合中。
collection.insert(1);   // 返回 false，因为集合包含 1。
                        // 将另一个 1 插入到集合中。集合现在包含 [1,1]。
collection.insert(2);   // 返回 true，因为集合不包含 2。
                        // 将 2 插入到集合中。集合现在包含 [1,1,2]。
collection.getRandom(); // getRandom 应当:
                        // 有 2/3 的概率返回 1,
                        // 1/3 的概率返回 2。
collection.remove(1);   // 返回 true，因为集合包含 1。
                        // 从集合中移除 1。集合现在包含 [1,2]。
collection.getRandom(); // getRandom 应该返回 1 或 2，两者的可能性相同。

 

提示:

  • -231 <= val <= 231 - 1
  • insert, remove 和 getRandom 最多 总共 被调用 2 * 105 次
  • 当调用 getRandom 时，数据结构中 至少有一个 元素

代码结果

运行时间: 297 ms, 内存: 69.7 MB

// 思路: 使用Java Stream实现 insert, remove, getRandom 方法。
// 利用Collectors.groupingBy收集元素及其索引，借助 Optional 操作来处理移除元素。
 
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
 
public class RandomizedCollectionStream {
    private List<Integer> nums;
    private Map<Integer, Set<Integer>> locs;
    private Random rand;
 
    public RandomizedCollectionStream() {
        nums = new ArrayList<>();
        locs = new HashMap<>();
        rand = new Random();
    }
 
    public boolean insert(int val) {
        boolean notContains = locs.computeIfAbsent(val, k -> new HashSet<>()).isEmpty();
        locs.get(val).add(nums.size());
        nums.add(val);
        return notContains;
    }
 
    public boolean remove(int val) {
        return Optional.ofNullable(locs.get(val))
                .filter(set -> !set.isEmpty())
                .map(set -> {
                    int loc = set.iterator().next();
                    set.remove(loc);
                    if (set.isEmpty()) locs.remove(val);
                    int lastElement = nums.get(nums.size() - 1);
                    nums.set(loc, lastElement);
                    locs.get(lastElement).add(loc);
                    locs.get(lastElement).remove(nums.size() - 1);
                    nums.remove(nums.size() - 1);
                    return true;
                })
                .orElse(false);
    }
 
    public int getRandom() {
        return nums.stream()
                .skip(rand.nextInt(nums.size()))
                .findFirst()
                .orElseThrow();
    }
}

解释

方法:

该题解使用哈希表 pos 和动态数组 value 来实现 O(1) 时间复杂度的插入、删除和获取随机元素操作。其中，哈希表 pos 用于存储每个元素在 value 中出现的下标位置集合，动态数组 value 用于存储实际的元素值。在插入时，将元素追加到 value 的末尾，并在 pos 中记录该元素的下标；在删除时，将要删除的元素与 value 的最后一个元素交换位置，然后删除最后一个元素，并更新 pos 中的下标信息；在获取随机元素时，直接从 value 中随机选择一个元素返回即可。

时间复杂度:

O(1)

空间复杂度:

O(n)

代码细节讲解

🦆
在`RandomizedCollection`中，如果`val`值重复多次，如何确保`remove`方法只删除一个实例？
▷
在`RandomizedCollection`的`remove`方法中，我们通过从`pos[val]`集合中弹出一个元素的下标实现删除一个实例。这个集合中存储了所有`val`值的下标，因此在调用`pop`方法时，它会随机移除并返回一个下标，这样保证了即使`val`值在数组`value`中重复多次，也只删除一个实例。删除操作完成后，会更新其他数据结构以保持一致性。
🦆
在完成删除操作时，你提到需要交换要删除的元素与数组最后一个元素的位置。这种方法在所有情况下都有效吗？例如，如果要删除的元素已经是数组中的最后一个元素，这里的逻辑是否需要调整？
▷
如果要删除的元素已经是数组`value`的最后一个元素，则无需进行交换。在这种情况下，直接从数组中弹出最后一个元素，并从`pos`的集合中移除相应的下标即可。这简化了操作，并避免了不必要的元素赋值，从而在所有情况下保持了方法的有效性。
🦆
当使用动态数组`value`和哈希表`pos`时，删除或插入操作是否可能导致哈希表和数组之间的不同步？例如，在删除操作中，如果`pop`操作或`set`更新失败了怎么办？
▷
确实存在数据不同步的风险，尤其是在遇到异常或操作失败时。为了防止数据不同步，需要确保在删除和插入操作中的每一步都能成功执行。在Python中，`pop`操作通常是安全的，但如果在更新集合`pos`时发生异常，如内存不足导致操作失败，就必须设计错误处理逻辑，例如使用事务性的操作或捕获异常来回滚到操作前的状态，以保持数据的一致性。
🦆
为什么在获取随机元素时，每个元素被返回的概率与集合中包含的相同值的数量线性相关？这是否意味着数组中每个位置被选中的可能性相等？
▷
这是因为在`RandomizedCollection`中，每个元素（包括重复的值）都以实际出现的次数存储在数组`value`中。因此，当从这个数组中随机选择一个元素时，每个位置被选中的概率确实是相等的，这导致每个元素被返回的概率与其在数组中的实际出现次数成正比。这种设计确保了随机选择的公平性，每个元素的选择概率与其频率成线性关系。

相关问题

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 方法时，数据结构中 至少存在一个 元素。
O(1) 时间插入、删除和获取随机元素链表随机节点