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方法时，数据结构中 至少存在一个 元素。
代码结果
运行时间: 247 ms, 内存: 0.0 MB
/*
* 思路：
* 使用一个 ArrayList 和一个 HashMap。
* ArrayList 存储元素，保证 O(1) 时间复杂度的随机访问。
* HashMap 存储元素值及其在 ArrayList 中的索引，以保证 O(1) 时间复杂度的插入和删除。
* 虽然 Java Stream 对此题帮助不大，但在 getRandom 方法中可以使用 Stream 进行改进。
*/
import java.util.*;
import java.util.stream.Collectors;
public class RandomizedSetStream {
private List<Integer> list;
private Map<Integer, Integer> map;
private Random rand;
public RandomizedSetStream() {
list = new ArrayList<>();
map = new HashMap<>();
rand = new Random();
}
public boolean insert(int val) {
if (map.containsKey(val)) {
return false;
}
map.put(val, list.size());
list.add(val);
return true;
}
public boolean remove(int val) {
if (!map.containsKey(val)) {
return false;
}
int index = map.get(val);
int lastElement = list.get(list.size() - 1);
list.set(index, lastElement);
map.put(lastElement, index);
list.remove(list.size() - 1);
map.remove(val);
return true;
}
public int getRandom() {
List<Integer> randomList = list.stream().collect(Collectors.toList());
return randomList.get(rand.nextInt(randomList.size()));
}
}
解释
方法:
这个题解使用了一个列表 values 和一个字典 val_to_index 来实现 O(1) 时间复杂度的插入、删除和随机获取元素。values 列表按插入顺序存储元素，val_to_index 字典则记录每个元素在 values 列表中的索引。插入元素时，将其添加到 values 列表末尾，并在 val_to_index 中记录其索引。删除元素时，先将要删除的元素与 values 列表的最后一个元素交换位置，然后删除列表最后一个元素并更新 val_to_index。获取随机元素时，直接在 values 列表中随机选择一个元素返回。
时间复杂度:
O(1)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在`remove`操作中，需要将要删除的元素与列表的最后一个元素交换位置？
▷🦆
随机获取元素时，所有元素的选择概率确实都是相同的吗？如果是，这是怎样实现的？
▷🦆
在`remove`操作中，如果删除的元素恰好是列表中的最后一个元素，是否还需要进行交换操作？这种情况下的处理逻辑是什么？
▷🦆
字典`val_to_index`的更新在交换元素后似乎只更新了最后一个元素的索引，为什么不需要更新被删除元素的索引？
▷相关问题
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 - 1insert,remove和getRandom最多 总共 被调用2 * 105次- 当调用
getRandom时，数据结构中 至少有一个 元素