面试经典算法150题系列-O（1）时间插入、删除和获取随机元素

序言：这题可能相对之前的题稍微代码量大一些，但是别急，我们只有理清思路，其实实现起来也挺简单，重在理解，我在实现代码部分特地还增加了一些变量方法的详细解释，担心有人不懂ArrayList集合和哈希集合操作，在最后还进行了补充，篇幅较长，望君细细品读。

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 。

实现思路：

我们需要实现O（1）时间复杂度的时间插入、删除和获取随机元素
单独使用ArrayList集合或哈希集合，都没有办法实现，因为哈希集合不方便实现获取随机元素，ArrayList集合查询操作无法满足条件。这时不妨想想，哈希集合查询元素的时间复杂度为O(1),ArrayList集合删除最后一个元素，以及插入一个元素到最后都为O（1），且可以实现随机访问元素。
这样一想，我们是不是可以将二者进行结合呢？

因此我们先来进行对象初始化，需要定义3个对象：

（1）定义ArrayList集合对象：用于存储元素和删除元素

（2）定义哈希集合对象：用于查询元素

（3）定义随机数对象用于获取随机索引

然后进行方法的构思：

insert 方法首先检查值是否已经存在于HashMap中，如果存在，则返回false。如果不存在，将值添加到ArrayList的末尾，并在HashMap中记录这个值到其索引的映射。
remove 方法检查值是否存在于HashMap中，如果不存在，则返回false。如果存在，找到这个值的索引，将ArrayList的最后一个元素移动到要删除的元素的位置，并更新HashMap中的索引。然后，从ArrayList中删除最后一个元素，并从HashMap中删除对应的映射。
getRandom 方法使用Random对象生成一个随机索引，并从ArrayList中返回该索引处的元素。

实现代码：

import java.util.ArrayList; // 导入ArrayList类
import java.util.HashMap;   // 导入HashMap类
import java.util.Random;    // 导入Random类// 定义RandomizedSet类
class RandomizedSet {// 使用HashMap存储数字到索引的映射private HashMap<Integer, Integer> numToIndex;// 使用ArrayList存储集合中的所有数字private ArrayList<Integer> nums;// Random对象用于生成随机数private Random rand;// 构造函数，初始化HashMap、ArrayList和Random对象public RandomizedSet() {numToIndex = new HashMap<>();nums = new ArrayList<>();rand = new Random();}// 插入操作，如果元素已存在则返回false，否则插入并返回truepublic boolean insert(int val) {// 检查元素是否已存在if (numToIndex.containsKey(val)) {return false;}// 将元素添加到ArrayList的末尾，并记录其索引numToIndex.put(val, nums.size());nums.add(val);return true;}// 删除操作，如果元素不存在则返回false，否则删除并返回truepublic boolean remove(int val) {// 检查元素是否存在if (!numToIndex.containsKey(val)) {return false;}// 获取要删除元素的索引int removeIndex = numToIndex.get(val);// 获取ArrayList的最后一个元素int lastElement = nums.get(nums.size() - 1);// 将最后一个元素放到要删除的元素的位置nums.set(removeIndex, lastElement);// 更新最后一个元素在HashMap中的索引numToIndex.put(lastElement, removeIndex);// 从ArrayList中移除最后一个元素nums.remove(nums.size() - 1);// 从HashMap中移除要删除元素的映射numToIndex.remove(val);return true;}// 随机获取一个元素public int getRandom() {// 生成一个随机索引int randomIndex = rand.nextInt(nums.size());// 返回ArrayList中随机索引处的元素return nums.get(randomIndex);}
}
import java.util.ArrayList; // 导入ArrayList类
import java.util.HashMap;   // 导入HashMap类
import java.util.Random;    // 导入Random类// 定义RandomizedSet类
class RandomizedSet {// 使用HashMap存储数字到索引的映射private HashMap<Integer, Integer> numToIndex;// 使用ArrayList存储集合中的所有数字private ArrayList<Integer> nums;// Random对象用于生成随机数private Random rand;// 构造函数，初始化HashMap、ArrayList和Random对象public RandomizedSet() {numToIndex = new HashMap<>();nums = new ArrayList<>();rand = new Random();}// 插入操作，如果元素已存在则返回false，否则插入并返回truepublic boolean insert(int val) {// 检查元素是否已存在if (numToIndex.containsKey(val)) {return false;}// 将元素添加到ArrayList的末尾，并记录其索引numToIndex.put(val, nums.size());nums.add(val);return true;}// 删除操作，如果元素不存在则返回false，否则删除并返回truepublic boolean remove(int val) {// 检查元素是否存在if (!numToIndex.containsKey(val)) {return false;}// 获取要删除元素的索引int removeIndex = numToIndex.get(val);// 获取ArrayList的最后一个元素int lastElement = nums.get(nums.size() - 1);// 将最后一个元素放到要删除的元素的位置nums.set(removeIndex, lastElement);// 更新最后一个元素在HashMap中的索引numToIndex.put(lastElement, removeIndex);// 从ArrayList中移除最后一个元素nums.remove(nums.size() - 1);// 从HashMap中移除要删除元素的映射numToIndex.remove(val);return true;}// 随机获取一个元素public int getRandom() {// 生成一个随机索引int randomIndex = rand.nextInt(nums.size());// 返回ArrayList中随机索引处的元素return nums.get(randomIndex);}
}// 下面的代码是给测试用例看的，实际使用时不需要
/*** Your RandomizedSet object will be instantiated and called as such:* RandomizedSet obj = new RandomizedSet();* boolean param_1 = obj.insert(val);* boolean param_2 = obj.remove(val);* int param_3 = obj.getRandom();*/

下面是对每个部分的详细解释：

类成员变量

private HashMap<Integer, Integer> numToIndex;：一个哈希表，用于存储集合中每个数字到其在ArrayList中的索引的映射。这使得我们可以快速地访问和更新元素的位置。
private ArrayList<Integer> nums;：一个动态数组，用于存储集合中的所有元素。这允许我们快速地随机访问任何一个元素。
private Random rand;：一个随机数生成器，用于getRandom方法中生成随机索引。

构造函数

public RandomizedSet()：构造函数初始化了HashMap和ArrayList，并创建了一个随机数生成器实例。

方法

public boolean insert(int val)：向集合中插入一个新元素。
- 首先检查该元素是否已经存在于HashMap中（即集合中是否已包含该值）。
- 如果已存在，返回false表示插入失败。
- 如果不存在，将元素添加到ArrayList的末尾，并在HashMap中记录这个新元素的值和它在ArrayList中的索引。
- 返回true表示插入成功。
public boolean remove(int val)：从集合中删除一个元素。
- 首先检查该元素是否存在于HashMap中。
- 如果不存在，返回false表示删除失败。
- 如果存在，找到该元素在ArrayList中的索引，然后执行以下步骤：
  - 将ArrayList最后一个元素与要删除的元素交换位置。
  - 更新HashMap中最后一个元素的新索引。
  - 从ArrayList中删除最后一个元素。
  - 从HashMap中移除被删除元素的映射。
- 返回true表示删除成功。
public int getRandom()：随机返回集合中的一个元素。
- 使用Random对象生成一个0到ArrayList长度减1的随机索引。
- 返回ArrayList中该索引处的元素。

性能考虑

insert和remove操作的平均时间复杂度是O(1)，因为哈希表的插入、查找和删除操作都是O(1)，而数组元素的交换和删除操作也是O(1)。
getRandom操作的时间复杂度是O(1)，因为生成随机数和随机访问数组元素都是常数时间操作。

这种实现确保了RandomizedSet的所有操作都能以平均常数时间完成，同时支持随机访问元素。

知识补充：哈希集合和ArrayList集合（特点和操作）

·哈希集合和ArrayList集合的特点：

哈希集合（HashSet）

基于哈希表: HashSet 基于哈希表实现，通过哈希函数将元素分布到不同的桶（bucket）中。
元素唯一性: 只允许存储不重复的元素，即集合中的每个元素都是唯一的。
无序性: 元素在集合中没有特定的顺序，它们是无序的。
快速查找: 由于基于哈希表，HashSet 提供了快速的查找能力，平均时间复杂度为 O(1)。
动态扩容: 当元素数量增加到一定程度时，HashSet 会进行扩容以保持操作的效率。
常用操作: 提供了添加（add）、删除（remove）、检查存在性（contains）等操作。
内存占用: 通常比 ArrayList 占用更多的内存，因为需要存储额外的哈希表信息。

ArrayList

基于动态数组: ArrayList 是一个动态数组的实现，可以动态地增长和缩小。
元素有序: 元素在 ArrayList 中按照它们被插入的顺序排列，即元素是有序的。
快速随机访问: 允许快速随机访问任何位置的元素，时间复杂度为 O(1)。
插入和删除操作: 在列表末尾添加元素是 O(1) 的操作，但在中间或开始插入或删除元素可能需要 O(n) 的时间，因为可能需要移动其他元素。
容量调整: 当 ArrayList 的容量不足以容纳新元素时，会自动调整容量，这涉及到创建一个新的数组和复制旧元素。
常用操作: 提供了添加（add）、删除（remove）、获取元素（get）、设置元素（set）等操作。
内存连续性: ArrayList 的内存是连续的，这使得它在遍历和随机访问时非常高效。

总结

哈希集合适合于需要快速查找和确保元素唯一性的场景。
ArrayList 适合于需要快速随机访问元素和保持元素插入顺序的场景。

选择使用哪种集合类型取决于具体的应用需求和性能考虑。理解每种集合的特点可以帮助开发者做出更合适的选择。

·哈希集合和ArrayList集合的操作

ArrayList和HashMap是Java集合框架中的两个非常重要的类，分别提供了动态数组和哈希表的实现。下面是它们的基本操作：

ArrayList 基本操作

添加元素
- add(E e): 向列表末尾添加一个元素。
- add(int index, E element): 在指定位置插入一个元素。
获取元素
- get(int index): 返回指定位置的元素。
设置元素
- set(int index, E element): 用指定元素替换列表中指定位置的元素。
删除元素
- remove(Object o): 移除列表中第一次出现的指定元素。
- remove(int index): 删除指定位置的元素。
大小操作
- size(): 返回列表中的元素数量。
遍历
- 使用for-each循环或迭代器遍历列表中的元素。
清空列表
- clear(): 移除列表中的所有元素。

HashMap 基本操作

添加键值对
- put(K key, V value): 将指定的值与此映射中的指定键关联。
获取值
- get(Object key): 返回指定键所映射的值。
删除键值对
- remove(Object key): 如果存在一个键的映射关系，则将其从映射中移除。
检查存在性
- containsKey(Object key): 如果映射包含键的映射关系，则返回true。
键集操作
- keySet(): 返回映射中包含的键的Set视图。
值集操作
- values(): 返回映射中包含的值的Collection视图。
条目集操作
- entrySet(): 返回映射中包含的键值映射关系的Set视图。
大小操作
- size(): 返回映射中键值对的数量。
清空映射
- clear(): 移除映射中的所有键值对。
遍历
- 使用for-each循环或迭代器遍历键、值或键值对。

示例代码

以下是一些使用ArrayList和HashMap的示例代码：

import java.util.ArrayList;
import java.util.HashMap;public class Example {public static void main(String[] args) {// ArrayList示例ArrayList<String> list = new ArrayList<>();list.add("Apple"); // 添加元素System.out.println(list.get(0)); // 获取元素list.set(0, "Banana"); // 设置元素list.remove("Apple"); // 删除元素System.out.println(list.size()); // 获取大小list.clear(); // 清空列表// HashMap示例HashMap<Integer, String> map = new HashMap<>();map.put(1, "Apple"); // 添加键值对String value = map.get(1); // 获取值map.remove(1); // 删除键值对boolean contains = map.containsKey(1); // 检查键是否存在System.out.println(map.size()); // 获取大小map.clear(); // 清空映射}
}

这些基本操作为使用ArrayList和HashMap提供了强大的灵活性，使得它们成为处理集合数据时的首选工具。