力扣面试经典算法150题：O(1) 时间插入、删除和获取随机元素

O(1) 时间插入、删除和获取随机元素

今天的题目是力扣面试经典150题中的数组的中等难度题： O(1) 时间插入、删除和获取随机元素。

题目链接：https://leetcode.cn/problems/insert-delete-getrandom-o1/description/?envType=study-plan-v2&envId=top-interview-150

问题描述

实现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 表示成功插入
randomizedSet.remove(2); // 尝试移除 2，返回 false 表示未找到
randomizedSet.insert(2); // 插入 2，返回 true 表示成功插入
randomizedSet.getRandom(); // 随机返回 1 或 2，这里假设返回 2
randomizedSet.remove(1); // 移除 1，返回 true 表示成功移除
randomizedSet.insert(2); // 尝试插入 2，返回 false 表示已存在
randomizedSet.getRandom(); // 随机返回 2，因为现在集合中只有 2

题目分析

题目要求我们实现一个类，这个类可以写入，删除或随机获取某个元素，并且要求每个函数的平均时间复杂度为O(1)。

不要被要实现一个类迷惑，其实就是要求我们设计一个数据结构和函数算法，并且要求函数的时间复杂度在规定范围之内就行。

为了实现在 O(1) 时间内完成插入、删除和获取随机元素的操作，我们需要设计一种数据结构，能够快速定位元素的位置，并且在删除元素时不影响随机获取的性能。

解题思路

这个题目需要通过组合我们常用的数据结构来实现需求，考验的就是我们对常见的数据结构的理解与掌握。毕竟是中等难度的题目，能够正确理解掌握现有的数据结构并通过组合实现特定场景的优秀算法，已经是很不错了。

我们先梳理一下常见的数据结构：数组，链表，哈希表，队列，堆，栈。这些数据结构各有各的特点，这里不一一细讲，这东西细讲起来能不是一下两下能讲完的，目前我们需要知道的就是，想完成题目要求，我们需要在这些数据结构中组合使用。

看看题目中的要求，不存在时才能新增，存在时才能删除。也就是说，在执行这两个函数的时候，我们需要先知道元素在不在我们设定的数据结构中。

这个时候，哈希表说：老弟，这个我熟啊！

但是哈希表的新增与删除通常情况下是符合条件的，但是极端情况下是O(n)。此外，获取随机元素通常我们需要遍历整个哈希表才能实现，这个时间复杂度是O(n)。

假如我们在哈希表的基础上，加其他的数据结构来实现是不是就可行呢？因为之前我们就分析过，这个题目本身就是需要通过组合多种数据结构实现的。那么获取随机元素的同时，新增删除又能是O(1)的时间复杂度的，又有谁能？

数组：哥，你看看我啊！这里！

没错，数组，作为最常用并且最先认识的数据结构，有下标的情况下，随机获取是O(1)的复杂度，新增和删除最后一个元素也是O(1)的复杂度。

那么，使用data-index的键值对方式保存到哈希表中，将实际元素放入到数组中。是不是满足新增删除前的判断，并且新增，获取随机元素的时间复杂度都是O(1)，唯一没满足的就是删除，因为我们不能保证每次都删除最后一位元素。但是，数组的修改方法，在有下标的时候，时间复杂度是O(1)。正所谓没有条件，创造条件也要上，我们直接把需要删除的元素修改到最后一位，再删除，是不是就变成删除最后一位元素，时间复杂度为O(1)了。

总结一下上面的分析内容：

哈希表 + 动态数组：使用哈希表来存储元素及其在数组中的位置，使用动态数组来存储实际的元素。
优化删除操作：为了保证删除操作能在 O(1) 时间内完成，可以将要删除的元素与数组的最后一个元素交换位置，然后删除最后一个元素。

那么，开始表演！

实际算法代码

以下是使用上述思路的 Java 实现：

import java.util.HashMap;
import java.util.Map;class RandomizedSet {private Map<Integer, Integer> valToIndex;private int[] values;private int size;public RandomizedSet() {valToIndex = new HashMap<>();// 初始容量values = new int[8];size = 0;}public boolean insert(int val) {if (valToIndex.containsKey(val)) return false;if (size == values.length) {resizeArray();}valToIndex.put(val, size);values[size] = val;size++;return true;}public boolean remove(int val) {if (!valToIndex.containsKey(val)) return false;int index = valToIndex.get(val);int lastElement = values[size - 1];values[index] = lastElement;valToIndex.put(lastElement, index);valToIndex.remove(val);size--;return true;}public int getRandom() {return values[(int) (Math.random() * size)];}private void resizeArray() {int[] newArray = new int[values.length * 2];System.arraycopy(values, 0, newArray, 0, values.length);values = newArray;}
}