LeetCode题练习与总结：O(1) 时间插入、删除和获取随机元素--380
一、题目描述
实现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 。
提示：
-2^31 <= val <= 2^31 - 1- 最多调用
insert、remove和getRandom函数2 *10^5次 - 在调用
getRandom方法时，数据结构中 至少存在一个 元素。
二、解题思路
为了实现 RandomizedSet 类，我们需要保证 insert、remove 和 getRandom 操作的平均时间复杂度为 O(1)。为了达到这个目标，我们可以使用以下数据结构：
- 动态数组（ArrayList）：用于存储集合中的元素，这样可以在 O(1) 时间内通过索引访问到任何元素。
- 哈希表（HashMap）：用于存储每个元素值与其在动态数组中索引的映射，这样可以在 O(1) 时间内检查元素是否存在以及获取其索引。
以下是解题思路：
-
插入操作（insert）：
- 使用哈希表检查元素是否已存在。
- 如果不存在，将其添加到动态数组的末尾，并在哈希表中记录其索引。
-
删除操作（remove）：
- 使用哈希表检查元素是否存在以及其索引。
- 如果存在，将数组中该元素与最后一个元素交换位置，然后删除数组末尾的元素，并更新哈希表中的索引映射。
-
获取随机元素（getRandom）：
- 由于数组中的元素是连续存储的，我们可以通过生成一个随机索引来直接访问数组中的随机元素。
三、具体代码
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;public class RandomizedSet {private Map<Integer, Integer> indexMap;private List<Integer> nums;private Random rand;public RandomizedSet() {indexMap = new HashMap<>();nums = new ArrayList<>();rand = new Random();}public boolean insert(int val) {if (indexMap.containsKey(val)) {return false;}indexMap.put(val, nums.size());nums.add(val);return true;}public boolean remove(int val) {if (!indexMap.containsKey(val)) {return false;}int lastElement = nums.get(nums.size() - 1);int idxToRemove = indexMap.get(val);nums.set(idxToRemove, lastElement);indexMap.put(lastElement, idxToRemove);nums.remove(nums.size() - 1);indexMap.remove(val);return true;}public int getRandom() {return nums.get(rand.nextInt(nums.size()));}
}
这段代码实现了 RandomizedSet 类，满足了题目要求的 O(1) 时间复杂度。每次插入和删除操作都会更新哈希表和动态数组，而获取随机元素则直接从动态数组中随机选择一个索引。
四、时间复杂度和空间复杂度
1. 时间复杂度
-
构造函数
RandomizedSet():- 初始化
indexMap和nums的时间复杂度是 O(1)。 - 初始化
rand的时间复杂度也是 O(1)。 - 因此，总的时间复杂度是 O(1)。
- 初始化
-
方法
insert(int val):- 检查元素是否存在于哈希表中，时间复杂度是 O(1)。
- 如果元素不存在，则添加到动态数组和哈希表中，添加到数组和哈希表的操作时间复杂度都是 O(1)。
- 因此，总的时间复杂度是 O(1)。
-
方法
remove(int val):- 检查元素是否存在于哈希表中，时间复杂度是 O(1)。
- 如果元素存在，则需要交换待删除元素与数组末尾元素的位置，并更新哈希表，这些操作的时间复杂度都是 O(1)。
- 删除数组末尾元素，时间复杂度是 O(1)。
- 从哈希表中删除元素，时间复杂度也是 O(1)。
- 因此，总的时间复杂度是 O(1)。
-
方法
getRandom():- 生成随机索引，时间复杂度是 O(1)。
- 通过索引访问数组元素，时间复杂度是 O(1)。
- 因此，总的时间复杂度是 O(1)。
2. 空间复杂度
-
构造函数
RandomizedSet():indexMap和nums都是动态数据结构，它们的空间复杂度取决于集合中元素的数量。rand是一个轻量级的对象，它占用的空间可以认为是 O(1)。- 因此，总的空间复杂度是 O(n)，其中 n 是集合中元素的数量。
-
方法
insert(int val):- 没有使用额外的空间，除了在
nums和indexMap中存储元素。 - 因此，空间复杂度是 O(1)。
- 没有使用额外的空间，除了在
-
方法
remove(int val):- 同样，没有使用额外的空间。
- 因此，空间复杂度是 O(1)。
-
方法
getRandom():- 没有使用额外的空间。
- 因此，空间复杂度是 O(1)。
3. 总结
-
时间复杂度:
- 构造函数：O(1)
insert(int val)：O(1)remove(int val)：O(1)getRandom()：O(1)
-
空间复杂度:
- 构造函数：O(n)
insert(int val)：O(1)remove(int val)：O(1)getRandom()：O(1)
其中 n 是集合中元素的数量。注意，虽然单个操作的空间复杂度是 O(1)，但是随着集合中元素数量的增加，整体空间需求会线性增长。
五、总结知识点
-
类定义:
public class RandomizedSet定义了一个公共类RandomizedSet。
-
成员变量:
private Map<Integer, Integer> indexMap;定义了一个私有成员变量indexMap，用于存储元素值与其在动态数组中的索引的映射。private List<Integer> nums;定义了一个私有成员变量nums，用于存储集合中的元素。private Random rand;定义了一个私有成员变量rand，用于生成随机数。
-
构造函数:
public RandomizedSet()是类的构造函数，用于初始化成员变量。
-
哈希表（HashMap）:
indexMap是一个HashMap，它提供了 O(1) 时间复杂度的查找、插入和删除操作。
-
动态数组（ArrayList）:
nums是一个ArrayList，它支持动态数组操作，如添加、删除和通过索引访问元素。
-
随机数生成（Random）:
rand是Random类的一个实例，用于生成随机数。
-
方法定义:
public boolean insert(int val)定义了一个公共方法，用于向集合中插入一个元素。public boolean remove(int val)定义了一个公共方法，用于从集合中移除一个元素。public int getRandom()定义了一个公共方法，用于从集合中随机获取一个元素。
-
条件判断:
if (indexMap.containsKey(val))用于检查元素是否已经在集合中。if (!indexMap.containsKey(val))用于检查元素是否不在集合中。
-
哈希表操作:
indexMap.put(val, nums.size());将元素值和其在数组中的索引插入哈希表。indexMap.remove(val);从哈希表中移除一个元素。
-
数组操作:
nums.add(val);在数组的末尾添加一个元素。nums.set(idxToRemove, lastElement);通过索引设置数组中的元素。nums.remove(nums.size() - 1);移除数组末尾的元素。
-
随机数的使用:
rand.nextInt(nums.size());生成一个介于 0（包含）和nums.size()（不包含）之间的随机整数，用于随机访问数组元素。
-
返回值:
return true;和return false;分别用于表示操作成功或失败。return nums.get(rand.nextInt(nums.size()));返回一个随机选择的数组元素。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。