Leetcode经典题9--O(1)时间的插入,添加和获取随机元素

server/2024/12/15 20:48:52/

题目描述:

实现RandomizedSet 类:

  • RandomizedSet() 初始化 RandomizedSet 对象
  • bool insert(int val) 当元素 val 不存在时,向集合中插入该项,并返回 true ;否则,返回 false 。
  • bool remove(int val) 当元素 val 存在时,从集合中移除该项,并返回 true ;否则,返回 false 。
  • int getRandom() 随机返回现有集合中的一项(测试用例保证调用此方法时集合中至少存在一个元素)。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数,并满足每个函数的 平均 时间复杂度为 O(1) 。

解题方案:

方式一:变长数组+哈希表

算法思想:变长数组可以在 O(1) 的时间内完成获取随机元素操作,但是由于无法在 O(1) 的时间内判断元素是否存在,因此不能在 O(1) 的时间内完成插入和删除操作。哈希表可以在 O(1) 的时间内完成插入和删除操作,但是由于无法根据下标定位到特定元素,因此不能在 O(1) 的时间内完成获取随机元素操作。为了满足插入、删除和获取随机元素操作的时间复杂度都是 O(1),需要将变长数组和哈希表结合,变长数组中存储元素,哈希表中存储每个元素在变长数组中的下标。

插入操作时,首先判断 val 是否在哈希表中,如果已经存在则返回 false,如果不存在则插入 val,操作如下:

在变长数组的末尾添加 val;

在添加 val 之前的变长数组长度为 val 所在下标 index,将 val 和下标 index 存入哈希表;

返回 true。

删除操作时,首先判断 val 是否在哈希表中,如果不存在则返回 false,如果存在则删除 val,操作如下:

从哈希表中获得 val 的下标 index;

将变长数组的最后一个元素 last 移动到下标 index 处,在哈希表中将 last 的下标更新为 index;

在变长数组中删除最后一个元素,在哈希表中删除 val;

返回 true。

删除操作的重点在于将变长数组的最后一个元素移动到待删除元素的下标处,然后删除变长数组的最后一个元素。该操作的时间复杂度是 O(1),且可以保证在删除操作之后变长数组中的所有元素的下标都连续,方便插入操作和获取随机元素操作。

获取随机元素操作时,由于变长数组中的所有元素的下标都连续,因此随机选取一个下标,返回变长数组中该下标处的元素。

实现代码:

class RandomizedSet {List<Integer> nums;Map<Integer,Integer> indics;Random random;public RandomizedSet() {nums=new ArrayList<Integer>();indics=new HashMap<Integer,Integer>();random=new Random();}public boolean insert(int val) {if(indics.containsKey(val)){return false;}int index=nums.size();nums.add(val);indics.put(val,index);return true;}public boolean remove(int val) {if(!indics.containsKey(val)){return false;}int index=indics.get(val);int last=nums.get(nums.size()-1);nums.set(index,last);indics.put(last,index);nums.remove(nums.size()-1);indics.remove(val);return true;}public int getRandom() {int randomIndex=random.nextInt(nums.size());return nums.get(randomIndex);}
}
本题相关知识点
变长数组List 可以进行的相关操作

get(int index):用于获取指定索引位置的元素。

例如,List list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); int element = list.get(1);,这里element的值为2。

set(int index, Integer element):用于替换指定索引位置的元素,并返回被替换的元素。

例如,List list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); int oldElement = list.set(1, 4);,此时list变为[1, 4, 3],oldElement的值为2。

add(Integer element):在列表的末尾添加一个元素。

例如,List list = new ArrayList<>(); list.add(1); list.add(2);,则list变为[1, 2]。

add(int index, Integer element):在指定的索引位置插入一个元素,原索引位置及之后的元素向后移动一位。

例如,List list = new ArrayList<>(); list.add(1); list.add(3); list.add(1, 2);,则list变为[1, 2, 3]。

remove(int index):删除指定索引位置的元素,并返回被删除的元素。

例如,List list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); int removedElement = list.remove(1);,此时list变为[1, 3],removedElement的值为2。

remove(Integer element):删除列表中第一个出现的指定元素。

例如,List list = new ArrayList<>(); list.add(1); list.add(2); list.add(1); list.remove((Integer)1);,这里需要注意要将1转换为Integer类型,执行后list变为[2, 1]。

indexOf(Integer element):返回指定元素在列表中第一次出现的索引,如果不存在则返回-1。

例如,List list = new ArrayList<>(); list.add(1); list.add(2); list.add(1); int index = list.indexOf(1);,index的值为0。

lastIndexOf(Integer element):返回指定元素在列表中最后一次出现的索引,如果不存在则返回-1。

例如,List list = new ArrayList<>(); list.add(1); list.add(2); list.add(1); int index = list.lastIndexOf(1);,index的值为2。

contains(Integer element):判断列表是否包含指定元素,返回true或false。

例如,List list = new ArrayList<>(); list.add(1); list.add(2); boolean result = list.contains(1);,result的值为true。

size():返回列表中元素的个数。例如,List list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); int size = list.size();,size的值为3。

isEmpty():判断列表是否为空,返回true或false。例如,List list = new ArrayList<>(); boolean result = list.isEmpty();,result的值为true。

subList(int fromIndex, int toIndex):返回一个包含指定范围元素的子列表,左闭右开区间。例如,List list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); List subList = list.subList(0, 2);,subList为[1, 2]。

 

哈希表Map可以进行的相关操作

put(Integer key, Integer value):将指定的键值对添加到Map中,如果键已存在,则用新的值替换旧的值,并返回旧的值。

get(Integer key):根据指定的键获取对应的值,如果键不存在,则返回null。

getOrDefault(Integer key, Integer defaultValue):根据指定的键获取对应的值,如果键不存在,则返回默认值。

remove(Integer key):根据指定的键删除对应的键值对,并返回被删除的值,如果键不存在,则返回null。

keySet():返回Map中所有键的集合,可以通过遍历键集来获取对应的值。

values():返回Map中所有值的集合。

entrySet():返回Map中所有键值对的集合,每个键值对是一个Map.Entry对象,可以通过该对象获取键和值。

size():返回Map中键值对的数量。

isEmpty():判断Map是否为空,返回true或false。

containsKey(Integer key):判断Map中是否包含指定的键,返回true或false。

containsValue(Integer value):判断Map中是否包含指定的值,返回true或false。

 


http://www.ppmy.cn/server/150434.html

相关文章

【Linux服务器nginx前端部署详解】ubantu22.04,前端Vue项目dist打包

本文主要讲一下在Linux系统环境下&#xff08;以ubantu22.04为例&#xff09;&#xff0c;如何用nginx部署前端Vue项目打包的dist静态资源。有些具体的命令就不展开讲了&#xff0c;可以自行查看其他博主的文章&#xff0c;我主要讲整体的步骤和思路。 一、ubantu系统安装ngin…

PyTorch基本使用-线性回归案例

文章目录 1. 训练模型步骤2. 训练模型API3. 训练模型 学习目标&#xff1a;掌握PyTorch构建线性回归模型相关API 1. 训练模型步骤 我们使用 PyTorch 的各个组件来构建线性回归的实现。在pytorch中进行模型构建的整个流程一般分为四个步骤&#xff1a; 准备训练数据集构建要使…

《智能体开发实战(高阶)》四、系统化的日志周报智能体开发计划

智能体扩展与完善规划 为了将前几个章节的智能体逐步扩展为支持整个公司团队使用的高效工具,以下是分阶段的完善与扩写规划。每个阶段旨在提升功能覆盖范围、处理能力和用户体验,并为企业提供实际价值。 阶段一:基础功能完善 目标:巩固现有功能,提升健壮性和适用性。 支…

android 底层硬件通知webview 技术—未来之窗行业应用跨平台架构

String 未来之窗反向js2 "javascript:" "东方仙盟技术" "(\"nfc_reader\"," 未来之窗NFC ")"; cwpd_Web.evaluateJavascript(未来之窗反向js2, new ValueCallback<String>() { …

「Mac玩转仓颉内测版50」小学奥数篇13 - 动态规划入门

本篇将通过 Python 和 Cangjie 双语介绍动态规划的基本概念&#xff0c;并解决一个经典问题&#xff1a;斐波那契数列。学生将学习如何使用动态规划优化递归计算&#xff0c;并掌握编程中的重要算法思想。 关键词 小学奥数Python Cangjie动态规划斐波那契数列 一、题目描述 …

docker-4.迁移存储目录

docker pull 拉取镜像时候磁盘空间满,迁移/var/lib/docker目录 目录 1. 清理Docker占用的磁盘空间2.迁移 /var/lib/docker 目录3.开机自动挂载文件/etc/fstab4.docker国内镜像源1. 清理Docker占用的磁盘空间 清理空间: Docker System命令, 在《谁用光了磁盘?Docker System…

路由介绍.

RIB和FIB Routing Information Base&#xff08;RIB&#xff09;&#xff0c;即路由信息库&#xff0c;是存储在路由器或联网计算机中的一个电子表格或类数据库&#xff0c;它保存着指向特定网络地址的路径信息&#xff0c;包括路径的路由度量值。RIB的主要目标是实现路由协议…

docker容器内部启动jupyter notebook但是宿主机无法访问的解决方法

目录 1.问题2.解决方法 1.问题 在docker容器内启动了jupyter notebook&#xff0c;在宿主机内用如下的url无法访问 http://localhost:8888 http://127.0.0.1:8888 启动方法&#xff1a; jupyter notebook 2.解决方法 启动方法加上选项[ --ip‘*’]或者[–ip‘0.0.0.0’] 即启…