LeetCode-题目整理【5】:O(1) 时间插入、删除和获取随机元素
RandomizedSet结构体存在切片和哈希表的原因:
-
变长数组由于可以根据下标定位到特定元素,因此可以在 O(1)的时间内完成获取随机元素操作,但是由于无法在 O(1) 的时间内判断元素是否存在,因此不能在 O(1) 的时间内完成插入和删除操作。
-
哈希表可以在 O(1) 的时间内判断元素是否存在,因此可以在 O(1)的时间内完成插入和删除操作,但是不可以根据下标定位到特定元素,因此不能在 O(1) 的时间内完成获取随机元素操作。
为了满足插入、删除和获取随机元素操作的时间复杂度都是 O(1),需要将变长数组和哈希表结合,变长数组中存储元素,哈希表中存储每个元素在变长数组中的下标。
- 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 。
type RandomizedSet struct {nums []intindices map[int]int
}func Constructor() RandomizedSet {return RandomizedSet{nums: make([]int, 0),indices: make(map[int]int),}
}func (this *RandomizedSet) Insert(val int) bool {if _, ok := this.indices[val]; ok {return false}// 在变长数组的末尾添加 valthis.nums = append(this.nums, val)//在添加 val 之前的变长数组长度为 val所在下标 index,将 val和下标 index 存入哈希表;// 因为要保证插入的值唯一,因此需要放在key的位置this.indices[val] = len(this.nums) - 1return true
}func (this *RandomizedSet) Remove(val int) bool {idx, ok := this.indices[val]if !ok {return false}lastIdx := len(this.nums) - 1lastVal := this.nums[lastIdx]this.nums[idx] = lastValthis.indices[lastVal] = idxdelete(this.indices, val)this.nums = this.nums[:lastIdx]return true
}func (this *RandomizedSet) GetRandom() int {randIdx := rand.Intn(len(this.nums))return this.nums[randIdx]
}// 变长数组可以在 O(1)的时间内完成获取随机元素操作,但是由于无法在 O(1) 的时间内判断元素是否存在,因此不能在 O(1) 的时间内完成插入和删除操作。哈希表可以在 O(1)的时间内完成插入和删除操作,但是由于无法根据下标定位到特定元素,因此不能在 O(1) 的时间内完成获取随机元素操作。
//为了满足插入、删除和获取随机元素操作的时间复杂度都是 O(1),需要将变长数组和哈希表结合,变长数组中存储元素,哈希表中存储每个元素在变长数组中的下标。/**1. Your RandomizedSet object will be instantiated and called as such:2. obj := Constructor();3. param_1 := obj.Insert(val);4. param_2 := obj.Remove(val);5. param_3 := obj.GetRandom();*/
- 插入操作时,首先判断 val是否在哈希表中,如果已经存在则返回 false,如果不存在则插入 val,操作如下:
在变长数组的末尾添加 val;
在添加 val之前的变长数组长度为 val所在下标 index,将 val\textit{val}val 和下标 index 存入哈希表;
返回 true。 - 删除操作时,首先判断 val是否在哈希表中,如果不存在则返回 false,如果存在则删除 val,操作如下:
从哈希表中获得 val的下标 index;
将变长数组的最后一个元素 last移动到下标 index处,在哈希表中将 last 的下标更新为 index;
在变长数组中删除最后一个元素,在哈希表中删除 val;
返回 true。
删除操作的重点在于将变长数组的最后一个元素移动到待删除元素的下标处,然后删除变长数组的最后一个元素。该操作的时间复杂度是 O(1),且可以保证在删除操作之后变长数组中的所有元素的下标都连续,方便插入操作和获取随机元素操作。
(相当于把nums的最后一个元素lastval代替val在数组中的位置,同时也更新哈希表中lastval的值,最后截取数组,不要最后一个元素)
- 获取随机元素操作时,由于变长数组中的所有元素的下标都连续,因此随机选取一个下标,返回变长数组中该下标处的元素。
相关文章:
LeetCode-题目整理【5】:O(1) 时间插入、删除和获取随机元素
RandomizedSet结构体存在切片和哈希表的原因: 变长数组由于可以根据下标定位到特定元素,因此可以在 O(1)的时间内完成获取随机元素操作,但是由于无法在 O(1) 的时间内判断元素是否存在,因此不能在 O(1) 的时间内完成插入和删除操作…...
服务器感染了.wis[[Rast@airmail.cc]].wis勒索病毒,如何确保数据文件完整恢复?
导言: 在当今数字化的时代,恶意软件攻击已经变得越来越复杂和狡猾,[[MyFilewaifu.club]].wis [[backupwaifu.club]].wis[[Rastairmail.cc]].wis勒索病毒是其中的一种新威胁。本文91数据恢复将深入介绍[[MyFilewaifu.club]].wis [[backupwaif…...
ContentNegotiationManagerFactoryBean 内容协商
一.什么是内容协商 简单点说,就是同一资源,可以有多种表现形式,比如xml、json等,具体使用哪种表现形式,是可以协商的。 这是RESTfull的一个重要特性,Spring Web MVC也支持这个功能。 1.Spring MVC REST是如何决定采用…...
html css js 开发一个猜数字游戏
以下是一个使用HTML、CSS和JS开发的简单猜数字游戏的示例: HTML代码: <!DOCTYPE html> <html> <head><title>猜数字游戏</title><link rel"stylesheet" type"text/css" href"style.css&quo…...
HDD 东山再起,单块 30TB 起步新品想要颠覆储存行业
不得不承认,这年头机械硬盘(HDD)是越来越不受待见了。 体积大,耗电高,速度慢等多年祖传特点无不脱离当前消费者所追求的轻量化,高性能。 个人消费市场不约而同选择全面奔向固态硬盘(SSD&#x…...
【网络安全】-基本工具msf
secure 1、有此漏洞的目标主机2、无此漏洞的目标主机(常用) ps.本着兴趣爱好,加强电脑的安全防护能力,并严格遵守法律和道德规范。msf(metasploit framework)是一个开源的渗透测试框架,用于开发…...
Vue3的ref和reactive
目录 1、ref的基本使用 2、reactive的基本使用 3、ref操作dom 4、ref与reactive的异同 1、ref的基本使用 ref创建数据可以是基本类型也可以是引用类型 ref函数创建响应式数据,返回值是一个对象 模版中使用ref数据,省略.value,js代码中不能省略 获…...
Flink编程——风险欺诈检测
Flink 风险欺诈检测 文章目录 Flink 风险欺诈检测背景准备条件FraudDetectionJob.javaFraudDetector.java 代码分析执行环境创建数据源对事件分区 & 欺诈检测输出结果运行作业欺诈检测器 欺诈检测器 v1:状态欺诈检测器 v2:状态 时间完整的程序期望的…...
Day37 贪心算法 part06 738. 单调递增的数字 968. 监控二叉树
贪心算法 part06 738. 单调递增的数字 968. 监控二叉树 738. 单调递增的数字 class Solution { public:int monotoneIncreasingDigits(int n) {string strNum to_string(n);int tag strNum.size();for(int i strNum.size()-1; i>1; i--){if(strNum[i]<strNum[i-1]){…...
SpringBoot Redis入门(四)——Redis单机、哨兵、集群模式
单机模式:单台缓存服务器,开发、测试环境下使用;哨兵模式:主-从模式,提高缓存服务器的高可用和安全性。所有缓存的数据在每个节点上都一致。每个节点添加监听器,不断监听节点可用状态,一旦主节点…...
获取数组中的第一个、第二个、第三个......元素
常规操作可以直接使用索引(下标)获取: const arr [5,8,6,9,10] const first arr[0] //5 const second arr[1] //8 const third arr[2] //6 不使用索引,如何获取: const [first] [5,8,6,9,10] //…...
前端面试题(持续更新~~)
文章目录 一、基础1、数组常用的方法2、数组有哪几种循环方式?分别有什么作用?3、字符串常用的方法4、原型链5、闭包6、常见的继承7、cookie 、localstorage 、 sessionstrorage区别8、数组去重方法9、http 的请求方式10、数据类型的判断方法11、cookie …...
ubuntu下无法访问和ping通github的一种解决方法
近期在ubuntu下突然无法访问github了,ping也无法ping通,尝试过更换不同的网络也无济于事。后来在https://blog.csdn.net/weixin_48544978/article/details/133899687 这个文章中找到了解决办法。 运气比较好,只按照文章中的第一步将http://…...
C#,入门教程(28)——文件夹(目录)、文件读(Read)与写(Write)的基础知识
上一篇: C#,入门教程(27)——应用程序(Application)的基础知识https://blog.csdn.net/beijinghorn/article/details/125094837 C#知识比你的预期简单的多,但也远远超乎你的想象! 与文件相关的知识…...
开源大数据集群部署(六)Keytab文件生成
作者:櫰木 Keytab文件用于在不输入密码的情况下对主体(用户或服务)进行身份验证。以下是创建Kerberos身份验证的步骤。 1、创建keytab文件 除了使用明文密码登录之外,Kerberos还可以使用keytab密码文件登陆,现在为te…...
图神经网络X项目|基于图神经网络的电商行为的预测(5%)
文章目录 Jupyter Notebook 学习人工智能的好帮手数据集数据集下载数据集调用数据集应用技巧——获取不重复的编号数据集应用技巧——随机采样数据集应用技巧——抽取前N项进行模拟测试 数据集构建技巧一——查看数据集构建进度 Jupyter Notebook 学习人工智能的好帮手 【Jupy…...
仰暮计划|“说是操场,那就是个土坡,我们在那儿上边种种树啊,拔拔草,有的时候还会有同学来喂喂羊啥的,这都是我们的娱乐”
我是1948年农历二月份在河南省许昌市五女店镇的一个乡村里边出生的。从我记事的时候,中华人民共和国就已经成立了。当时是好多年,经历了三大改造呀、生产队呀、大队呀,乱七八糟的很多,估计你们现在这些孩子们啊,都没有…...
Java【代码 16】将word、excel文件转换为pdf格式和将pdf文档转换为image格式工具类分享
1.感谢 感谢小伙伴儿的分享: ● 不羁 ● 郭中天 整合调整后的工具类Gitee地址:https://gitee.com/yuanzhengme/java_application_aspose_demo 2.包含的工具类 ● WordToPdfUtil用于将word文档转换为pdf格式的工具类 ● ExcelToPdfUtil用于将excel文档…...
8亿日活的抖音,用“自我设限”谋求长期主义
文|新熔财经 作者|寒蝉鸣 随着手机近乎全民化的普及,在互联网上“冲浪”的人是越来越多了。 根据QuestMobile发布的《中国互联网核心趋势年度报告(2023)》,2023年,中国移动互联网月活跃用户规…...
Final Cut Pro v10.7.1中文版 专业级视频剪辑软件 兼容M
Final Cut Pro 是 macOS平台上最好的视频剪辑软件,基于Cocoa编写,支持多路多核心处理器,支持GPU加速,支持后台渲染,可编辑从标清到4K的各种分辨率视频,ColorSync管理的色彩流水线则可保证全片色彩的一致性。…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...
Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?
Pod IP 的本质与特性 Pod IP 的定位 纯端点地址:Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址(如 10.244.1.2)无特殊名称:在 Kubernetes 中,它通常被称为 “Pod IP” 或 “容器 IP”生命周期:与 Pod …...
抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...
【Veristand】Veristand环境安装教程-Linux RT / Windows
首先声明,此教程是针对Simulink编译模型并导入Veristand中编写的,同时需要注意的是老用户编译可能用的是Veristand Model Framework,那个是历史版本,且NI不会再维护,新版本编译支持为VeriStand Model Generation Suppo…...
