当前位置：首页 > news >正文

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

news 2025/8/14 15:28:45

一、题目分析

在这里插入图片描述

（一）功能需求

我们需要实现 RandomizedSet 类，包含以下功能：

RandomizedSet()：初始化数据结构。
bool insert(int val)：当元素 val 不存在时，插入该元素并返回 true；若已存在，返回 false 。
bool remove(int val)：当元素 val 存在时，移除该元素并返回 true；若不存在，返回 false 。
int getRandom()：随机返回现有集合中的一个元素，每个元素被返回的概率相同，且调用时集合至少有一个元素。

（二）核心挑战

要让插入、删除、获取随机元素操作的平均时间复杂度都达到 O(1) 。常规的数据结构往往难以单独满足这些要求，比如哈希表虽能高效插入和删除，但难以高效随机获取；动态数组便于随机获取，但插入和删除（尤其是中间元素）的时间复杂度较高。所以需要结合两者的优势来实现。

二、算法思想：哈希表 + 动态数组的协同运用

（一）哈希表（Map）的作用

使用 Map<Integer, Integer> 来存储元素 val 以及它在动态数组中的索引。这样可以：

插入元素时，快速判断元素是否已存在（通过 map.containsKey(val) ），时间复杂度为 O(1) 。
删除元素时，快速获取元素在动态数组中的位置，为后续在动态数组中高效删除元素做准备，时间复杂度为 O(1) 。

（二）动态数组（List）的作用

使用 List 来存储元素的值，方便进行随机获取操作。因为要实现随机获取元素且每个元素概率相同，我们可以利用 Random 类生成随机索引（范围是 0 到 list.size() - 1 ），然后通过 list.get(randomIndex) 快速获取元素，时间复杂度为 O(1) 。

（三）删除操作的优化

删除元素时，直接删除动态数组中间的元素时间复杂度会是 O(n) （需要移动元素）。为了优化这个操作，我们采用“交换删除”的策略：

获取要删除元素 val 在动态数组中的索引 reNumIndex ，以及动态数组最后一个元素 lastNum 。
将动态数组中 reNumIndex 位置的元素替换为 lastNum 。
更新 lastNum 在哈希表中的索引为 reNumIndex 。
删除动态数组的最后一个元素（时间复杂度 O(1) ），并从哈希表中移除 val 。这样就将删除操作的时间复杂度优化到了 O(1) 。

三、代码实现与详细注释

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;class RandomizedSet {// 哈希表，键为元素值，值为该元素在 numsList 中的索引Map<Integer, Integer> map; // 动态数组，存储元素的值，用于随机获取List<Integer> numsList; // 用于生成随机索引Random random; // 构造函数，初始化数据结构public RandomizedSet() {map = new HashMap<>();numsList = new ArrayList<>();random = new Random();}// 插入元素操作public boolean insert(int val) {// 判断元素是否已存在于哈希表中if (map.containsKey(val)) { return false; // 已存在，返回 false} else {// 将元素 val 与它在 numsList 中的索引（当前 numsList 的长度，因为即将添加到末尾）存入哈希表map.put(val, numsList.size()); // 将元素添加到 numsList 末尾numsList.add(val); return true; // 插入成功，返回 true}}// 删除元素操作public boolean remove(int val) {// 判断元素是否存在于哈希表中if (map.containsKey(val)) { // 获取动态数组最后一个元素的值int lastNum = numsList.get(numsList.size() - 1); // 获取要删除元素 val 在 numsList 中的索引int reNumIndex = map.get(val); // 将 numsList 中 reNumIndex 位置的元素替换为 lastNumnumsList.set(reNumIndex, lastNum); // 更新 lastNum 在哈希表中的索引为 reNumIndexmap.put(lastNum, reNumIndex); // 删除 numsList 的最后一个元素（时间复杂度 O(1) ）numsList.remove(numsList.size() - 1); // 从哈希表中移除要删除的元素 valmap.remove(val); return true; // 删除成功，返回 true} else {return false; // 元素不存在，返回 false}}// 随机获取元素操作public int getRandom() {// 生成一个 0 到 numsList.size() - 1 范围内的随机索引int randomIndex = random.nextInt(numsList.size()); // 根据随机索引获取元素并返回return numsList.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();*/

四、复杂度分析

（一）时间复杂度

插入操作（insert）：主要操作是哈希表的 containsKey 和 put ，以及动态数组的 add 操作。哈希表的这两个操作时间复杂度是 O(1) ，动态数组 add 操作（在末尾添加）时间复杂度也是 O(1) ，所以插入操作平均时间复杂度为 O(1) 。
删除操作（remove）：通过“交换删除”的优化，哈希表的 containsKey、get、put、remove 操作，以及动态数组的 get、set、remove（末尾删除）操作，时间复杂度都是 O(1) ，所以删除操作平均时间复杂度为 O(1) 。
随机获取操作（getRandom）：生成随机索引和动态数组的 get 操作时间复杂度都是 O(1) ，所以该操作平均时间复杂度为 O(1) 。