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

[M模拟] lc380. O(1) 时间插入、删除和获取随机元素(模拟+数据结构+脑筋急转弯+数组快捷删除技巧+项目思考)

news 来源：原创 2025/5/19 15:43:04

文章目录

- 1. 题目来源
- 2. 题目解析

1. 题目来源

链接：380. O(1) 时间插入、删除和获取随机元素

题单：

待补充

2. 题目解析

其实这个题目抽象一下的话在项目中也能出现，可能日常项目中没有算法基础的话，就很容易直接去进行新内存开辟、重复遍历等操作。尤其是在哈希表删除后，又需要进行一个相同概率返回的这个操作的时候。常见就有重新遍历哈希表到临时数组对象中，然后再依靠 rand 函数进行返回。

那么 $O (n)$ 次的查询情况下每一个遍历都是 $O (n)$ 的，那么整体的时间复杂度就是妥妥的 $O(n^2)$ 的，在高并发场景下，这就是妥妥的项目坑点啊。

思路：

构建一个哈希表、一个数组。哈希表用来存放 val 及数组中的该 val 的下标。数组用来存放全部元素，便于最后通过 rand 函数进行相同概率的直接返回，避免遍历哈希表。
主要是删除元素的时候，哈希表元素与数组元素怎么快速做到 $O (1)$ 删除。
- 我们只需要将数组最后一个元素与待删除元素调换位置，然后将最后一个元素 pop 出去就可以做到 $O (1)$ 的删除了。
- 同样上述的思想，在堆排序的向上调整、向下调整中也有用到。
- 在如何 $O (1)$ 删除单链表中的某一个节点元素的时候也有用到。

具体的看下如下代码即可，代码好理解，但如何运用到项目中去显著提高业务响应速度是值得我们去深思斟酌的。

时间复杂度： $O (1)$
空间复杂度： $O (n)$

type RandomizedSet struct {m map[int]int  // val--idx   存 val 值，及在 s 中的下标位置s []int        // val        存 val 值
}func Constructor() RandomizedSet {r := RandomizedSet {s: make([]int, 0, 32),m: make(map[int]int),}return r
}func (r *RandomizedSet) Insert(val int) bool {if _, ok := r.m[val]; ok {return false}r.m[val] = len(r.s)       // 新插入的 val 元素在 s 中的下标为总长度，及尾插r.s = append(r.s, val)return true
}func (r *RandomizedSet) Remove(val int) bool {id, ok := r.m[val]if !ok {return false}last := len(r.m) - 1  // 拿到最后一个元素的下标r.s[id] = r.s[last]   // 在数组中，用最后一个元素值覆盖掉要删除的元素值，方便等会直接删除最后一个元素就行r.m[r.s[last]] = id   // 在哈希表中，重新建立索引关系，最后一个元素的哈希值应该是待删除元素的数组中的下标位置r.s = r.s[:last]      // 切片操作，删除最后一个元素即可delete(r.m, val)      // 哈希表操作，删除哈希表元素即可return true
}func (r *RandomizedSet) GetRandom() int {return r.s[rand.Intn(len(r.s))]  // 随机化操作
}/*** Your RandomizedSet object will be instantiated and called as such:* obj := Constructor();* param_1 := obj.Insert(val);* param_2 := obj.Remove(val);* param_3 := obj.GetRandom();*/

[M模拟] lc380. O(1) 时间插入、删除和获取随机元素(模拟+数据结构+脑筋急转弯+数组快捷删除技巧+项目思考)

文章目录 1. 题目来源2. 题目解析 1. 题目来源链接：380. O(1) 时间插入、删除和获取随机元素题单： 待补充 2. 题目解析其实这个题目抽象一下的话在项目中也能出现，可能日常项目中没有算法基础的话，就很容易直接去进行新内…...

编程日记 2025/5/19 15:43:04

30~32.ppt

目录 30.导游小姚-介绍首都北京❗ 题目解析 31.小张-旅游产品推广文章题目解析 32.小李-水的知识❗ 题目解析 30.导游小姚-介绍首都北京❗ 题目解析新建幻灯片-从大纲-重置-检查设计→主题对话框→浏览主题：考生文件夹（注意&#x…...

编程日记 2025/5/14 17:33:38

一键查看电脑各硬件详细信息轻松查看电脑硬件参数

今天为大家推荐两款非常实用的电脑硬件查看软件，它们能够一键快速查看电脑的各种配置信息，使用起来非常方便。一键查看电脑各硬件详细信息这款软件是绿色版的，无需安装，打开即可使用，文件大小仅为900多KB&#xff0…...

编程日记 2025/5/19 15:34:02

java如何创建自定义异常？

在Java中，创建自定义异常通常需要继承Exception类或其子类。以下是创建自定义异常的基本步骤： 定义异常类：创建一个新的类，继承自Exception或RuntimeException（根据需要选择）。构造方法：提供一…...

编程日记 2025/5/14 2:35:52

2025/2/10 心得

第一题。J. C - Grand Garden (AI) 问题陈述在一个花坛里，有 NN 朵花，编号为 1,2,\ldots,N1,2,…,N。最初，所有花的高度都是 00。你将得到一个高度序列 h{h\_1,h\_2,h\_3,\ldots\} 作为输入。你希望通过重复以下“浇水”操作来将所有花的编…...

编程日记 2025/5/18 12:57:32

Visual Studio 2022 中使用 Google Test

要在 Visual Studio 2022 中使用 Google Test (gtest)，可以按照以下步骤进行： 安装 Google Test：确保你已经安装了 Google Test。如果没有安装，可以通过 Visual Studio Installer 安装。在安装程序中，找到并选择 Googl…...

编程日记 2025/5/19 9:15:48

软开关和硬开关

硬开关： 电路结构相对简单，一般只包含基本的开关管、电源、负载等元件，没有专门的谐振电路来辅助开关过程。开关管在导通或关断时，电压或电流的变化率非常快，形成急剧的开关过程。开通时，开关器件的电流…...

编程日记 2025/5/15 10:01:02

C++17中的std::clamp：限制值的范围

文章目录一、背景与动机二、std::clamp的定义三、使用示例示例1：基本用法示例2：浮点数和自定义类型四、实际应用场景1. 游戏开发2. 图形处理3. 数值计算五、注意事项六、总结在C17中， std::clamp是一个极为实用的算法，它能够…...

编程日记 2025/5/19 15:27:09

Python的

& 运算符可用于不同集合类型，它主要用于集合的交集操作下面分别介绍它在 set（集合）和 frozenset（不可变集合）这两种常见集合类型中的使用 set 类型 set 是 Python 中内置的可变集合类型，使用 & …...

编程日记 2025/5/15 15:56:48

计算机毕业设计Spark+大模型知网文献论文推荐系统知识图谱知网爬虫知网数据分析知网大数据知网可视化预测系统大数据毕业设计机器学习

温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 作者简介：Java领…...

编程日记 2025/5/14 7:43:39

13.8 聚焦应用场景的Prompt设计实战：从通用到领域专用的翻译质量跃升

聚焦应用场景的Prompt设计实战：从通用到领域专用的翻译质量跃升关键词：领域特定Prompt设计、翻译质量优化、动态术语控制、多阶段推理链、Prompt版本管理 1. 翻译Prompt设计核心原则 1.1 领域知识深度渗透 def build_medical_prompt(): return ChatPromptTemplate.from_…...

编程日记 2025/5/18 23:11:06

基础入门-HTTP数据包红蓝队研判自定义构造请求方法请求头修改状态码判断

知识点： 1、请求头&返回包-方法&头修改&状态码等 2、数据包分析-红队攻击工具&蓝队流量研判 3、数据包构造-Reqable自定义添加修改请求一、演示案例-请求头&返回包-方法&头修改&状态码等数据包客户端请求Request 请求方法 …...

编程日记 2025/5/15 5:25:31

Golang Web单体项目目录结构最佳实践

在Golang 开发Web 项目的过程中，如何组织目录结构是一项至关重要的任务。合理的目录结构不仅能提高代码的可维护性，还能为团队协作提供清晰的代码规范。为什么要设计合理的目录结构？ 在 Golang 项目中，代码的组织方式会影响开发…...

编程日记 2025/5/15 13:46:28

【系统架构设计师】体系结构文档化

目录 1. 说明2. 重要性3. 主要内容4. 编写原则5. 实践建议6. 例题6.1 例题1 1. 说明 1.绝大多数的体系结构都是抽象的，由一些概念上的构建组成。2.层的概念在任何程序设计语言中都不存在。3.要让系统分析员和程序员去实现体系结构，还必须将体系结构进行…...

编程日记 2025/5/12 21:00:28

C++性能优化—AI润色版

上接《C性能优化—人工底稿版》 C性能优化深度解析：从编码技巧到硬件协同 "过早优化是万恶之源" —— Donald Knuth 但合理的性能优化是优秀C工程师的核心能力。本文从编码实践到硬件原理，系统梳理C性能优化的知识体系。一、性能优化的哲学…...

编程日记 2025/5/18 14:00:34

继承（python）

一、基础知识 （一）定义：子类能继承父类所有的公有属性和公有方法（先使用子类的方法、属性） （二）格式： class 子类名（父类名）： #父类 class Ph…...

编程日记 2025/5/17 22:52:56

jmap使用

常用命令 jmap -heap PID jmap -histo PID | head -20 jmap -dump:formatb,fileheap_dump.hprof PID jmap 是 Java 开发工具包（JDK）提供的一个命令行工具，用于生成 Java 进程的内存映射信息。它可以帮助开发者分析 Java 堆内存的使用情况…...

编程日记 2025/5/18 11:01:41

Android的MQTT客户端实现

在 Android 平台上实现 MQTT 客户端的完整技术方案，涵盖基础实现、安全连接、性能优化和最佳实践： 一、技术选型与依赖配置推荐库 Eclipse Paho Android Service（官方维护，支持后台运行） gradle 复制 // build.gradl…...

编程日记 2025/5/19 15:23:30

Vue.js 如何自定义主题和样式

Vue.js 如何自定义主题和样式今天我们来聊聊如何在 Vue 项目中自定义主题和样式。无论是你想让自己的应用看起来独一无二，还是想快速适配设计稿，自定义主题和样式都是必不可少的一环。下面我将和大家分享几种常见的自定义方法和技巧。为什么要自定义…...

编程日记 2025/5/19 15:32:16

强化学习 DPO 算法：基于人类偏好，颠覆 PPO 传统策略

目录一、引言二、强化学习基础回顾（一）策略（二）价值函数三、近端策略优化（PPO）算法（一）算法原理（二）PPO 目标函数（三）代码示例&…...

编程日记 2025/5/17 23:50:08

线上HBase client返回超时异常分析 HBase callTimeout=60000

问题现象 HBase client直接返回超时异常 HBase callTimeout=60000, callDuration=60301: row ‘12649160863966c2790195059018040900010003320’ on table ‘Z_UPA’ at region=Z_UPA,1213d1a56,1184027415643. ba7224f83dbb09591a74b7059f17., hostname=abcd,60020,891863950…...

编程日记 2025/5/19 15:30:34

CTF中特别小的EXE是怎么生成的

我们在打CTF时候，出题的爷爷们给出的exe都很小就10k左右，有的甚至就5k，那时候我很郁闷啊。现在我也能了啊哈哈不多bb按如下操作： 我们来看看正常的release生成的代码# Copy #include "windows.h" int main(){ Messa…...

编程日记 2025/5/17 17:11:55

Python 字典（一个简单的字典）

在本章中，你将学习能够将相关信息关联起来的Python字典。你将学习如何访问和修改字典中的信息。鉴于字典可存储的信息量几乎不受限制，因此我们会演示如何遍历字典中的数据。另外，你还将学习存储字典的列表、存储列表的字典和存储字典的字典。…...

编程日记 2025/5/15 11:59:47

爬虫技巧汇总

一、UA大列表 USER_AGENT_LIST 是一个包含多个用户代理字符串的列表，用于模拟不同浏览器和设备的请求。以下是一些常见的用户代理字符串： USER_AGENT_LIST [Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; Trident/4.0; Hot Lingo 2.0),Mozilla…...

编程日记 2025/5/17 8:24:55

SCT2A15一款5.5V-100V 1.8A峰值电流限制高效率非同步降压DCDC转换器，SOT23-6L封装

SCT2A15是一款异步降压转换器，输入电压范围从5.5V到100V，可适应各种降压应用，是汽车、工业和照明应用的理想选择。 SCT2A15集成了975mΩ高侧MOSFET，峰值输出电流在Vin<60V时限制为1.8A，可支持高峰值电流的应用。 SC…...

编程日记 2025/5/19 15:28:48

数据结构——二叉树

好，上一篇我们已经讲过了堆，也已经了解了二叉树的基础知识后，我们今天来实现二叉树的相关代码。由于初始二叉树，由于现在对二叉树结构掌握还不够深入，为了降低学习成本，此处我们来手动快速创建一棵简单的二…...

编程日记 2025/5/14 2:03:17

六、通用异步收发器UART

6.1 UART简介 UART（Universal Asynchronous Receiver/Transmitter，通用异步收发传输器）是一种用于异步串行通信的硬件设备。它通过两根信号线（TX 和 RX）实现全双工通信，广泛应用于微控制器、计算机和外设之…...

编程日记 2025/5/18 6:34:36

基于Kotlin中Flow扩展重试方法

最近项目中统一采用Kotlin的Flow来重构了网络请求相关代码。目前的场景是，接口在请求的时候需要一个accessToken值，因为此值会过期或者不存在，需要刷新，因此最终方案是在使用Flow请求的时候先获取accessToken值然后再进行接口请求…...

编程日记 2025/5/16 12:09:34

在 Open WebUI+Ollama 上运行 DeepSeek-R1-70B 实现调用

在 Open WebUI Ollama 上运行 DeepSeek-R1-70B 实现调用您可以使用 Open WebUI 结合 Ollama 来运行 DeepSeek-R1-70B 模型，并通过 Web 界面进行交互。以下是完整的部署步骤。 1. 安装 Ollama Ollama 是一个本地化的大模型管理工具，它可以在本地运行 …...

编程日记 2025/5/15 0:45:20

速度超越DeepSeek！Le Chat 1100tok/s闪电回答，ChatGPT 4o和DeepSeek R1被秒杀？

2023年，当全球科技界还在ChatGPT引发的AI狂潮中沉浮时，一场来自欧洲的"静默革命"正悄然改变游戏规则。法国人工智能公司Mistral AI推出的聊天机器人Le Chat以"比ChatGPT快10倍"的惊人宣言震动业界，其背后承载的不仅是技术…...

编程日记 2025/5/15 12:48:27

如何使用C++将处理后的信号保存为PNG和TIFF格式

在信号处理领域，我们常常需要将处理结果以图像的形式保存下来，方便后续分析和展示。C提供了多种库来处理图像数据，本文将介绍如何使用stb_image_write库保存为PNG格式图像以及使用OpenCV库保存为TIFF格式图像。 1. PNG格式保存使用stb_ima…...

编程日记 2025/5/15 11:31:01

2 CXX-Qt #[cxx_qt::bridge] 宏指南

#[cxx_qt::bridge] 宏是用于在 Rust 中创建一个模块，该模块能够桥接 Rust 和 Qt（通过 C）之间的交互。它允许你将 Rust 类型暴露给 Qt 作为 QObject、Q_SIGNAL、Q_PROPERTY 等，同时也能够将 Qt 的特性和类型绑定到 Rust 中&#xf…...

编程日记 2025/5/18 9:56:29

PHP函数介绍—get_headers(): 获取URL的响应头信息

概述：在PHP开发中，我们经常需要获取网页或远程资源的响应头信息。PHP函数get_headers()能够方便地获取目标URL的响应头信息，并以数组形式返回。本文将介绍get_headers()函数的用法，以及提供一些相关的代码示例。 get_headers()函…...

编程日记 2025/5/17 15:48:02

C#树图显示目录下所有文件以及文件大小(使用Stack元组来替换递归)

接上篇 C#树图显示目录下所有文件以及文件大小_c# 查看文件夹里面有多少文件-CSDN博客上一篇我们使用递归的方法来实现绑定目录和文件到树图中,关键程序代码如下: 这里我们使用Stack的方式非递归方法来实现绑定目录和文件到树图: /// <summary>/// 递归方法&#xff…...

编程日记 2025/5/17 14:18:42

计算机毕业设计Python+Spark知识图谱医生推荐系统医生门诊预测系统医生数据分析医生可视化医疗数据分析医生爬虫大数据毕业设计机器学习

编程日记 2025/5/18 14:15:49

机器学习：朴素贝叶斯分类器

贝叶斯决策论是概率框架下实施决策的基本方法,对分类任务来说,在所有相关概率都已知的理想情形下,贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优的类别标记。贝叶斯定理是贝叶斯决策论的基础，描述了如何根据新的证据更新先验概率，贝叶斯定理&…...

编程日记 2025/5/15 6:43:58

解决 keep-alive 缓存组件中定时器干扰问题

当使用 keep-alive 缓存组件时，组件中的定时器可能会在组件被缓存后继续运行，从而干扰其他组件的逻辑。为了避免这种情况，可以通过以下方法解决： 1. 在组件的 deactivated 钩子中清理定时器 keep-alive 为缓存的组件提供了 acti…...

编程日记 2025/5/15 8:51:54

1-portal认证功能

很多时候公共网络需要提供安全认证功能，比如我们去星巴克或者商场、酒店，我们连接wifi上网的时候， 需要认证后才可以上网。用户可以主动访问已知的Portal认证网站，输入用户名和密码进行认证，这种开始Portal认证的方式…...

编程日记 2025/5/13 3:02:43

Kafka 的消费offset原来是使用ZK管理，现在新版本是怎么管理的？

目录基于 ZooKeeper 管理消费 offset 原理缺点新版本基于内部主题管理消费 offset 原理优点示例代码（Java）在 Kafka 早期版本中，消费者的消费偏移量（offset）是存储在 ZooKeeper 中的，但由于 ZooKeeper 并不适合高频读写操作，从 Kafka 0.9 版本开始，消费偏…...

编程日记 2025/5/12 17:22:00

LabVIEW图像水印系统

图像水印技术在数字图像处理中起着重要作用，它能够保护图像的版权、确保图像的完整性，并提供额外的信息嵌入。本项目旨在利用LabVIEW开发一个图像水印系统，实现图像水印的嵌入和提取功能，为数字图像处理提供便捷的工具。一、项目…...

编程日记 2025/5/18 11:12:35

Bash (Bourne-Again Shell)、Zsh (Z Shell)

文章目录 1. 历史背景2. 主要区别3. 功能对比自动补全插件和主题路径扩展提示符定制 4. 性能5. 使用场景6. 如何切换 Shell7. 总结以下是 Bash 和 Zsh 之间的主要区别，列成表格方便对比： 特性BashZsh默认Shell大多数Linux发行版默认ShellmacOS默认She…...

编程日记 2025/5/17 17:39:09

iOS AES/CBC/CTR加解密以及AES-CMAC

感觉iOS自带的CryptoKit不好用，有个第三方库CryptoSwift还不错，好巧不巧，清理过Xcode缓存后死活下载不下来，当然也可以自己编译个Framework，但是偏偏不想用第三方库了，于是研究了一下，自带的Com…...

编程日记 2025/5/18 1:29:42

蓝桥杯算法日记|贪心、双指针

3412 545 2928 2128 贪心学习总结： 1、一般经常用到sort（a，an）；【a[n]】排序，可以给整数排，也可以给字符串按照字典序排序 2、每次选最优双指针有序数组、字符串、二分查找、数字之和、反转字…...

编程日记 2025/5/18 11:06:40

浅谈Java Spring Boot 框架分析和理解

Spring Boot是一个简化Spring开发的框架，它遵循“约定优于配置”的原则，通过内嵌的Tomcat、Jetty或Undertow等容器，使得开发者能够快速构建独立运行的、生产级别的基于Spring框架的应用程序。Spring Boot包含了大量的自动配置功能&#xff0c…...

编程日记 2025/5/19 15:02:01

【系统架构设计师】操作系统 ③ ( 存储管理 | 页式存储弊端 - 段式存储引入 | 段式存储 | 段表 | 段表结构 | 逻辑地址的合法段地址判断 )

文章目录一、页式存储弊端 - 段式存储引入1、页式存储弊端 - 内存碎片2、页式存储弊端 - 逻辑结构不匹配3、段式存储引入二、段式存储简介1、段式存储2、段表3、段表结构4、段内地址 / 段内偏移5、段式存储优缺点6、段式存储与页式存储对比三、逻辑地址的合法段地址…...

编程日记 2025/5/18 1:30:52

网络编程-day4-TPC之文件传输

服务器 #include <stdio.h> #include <string.h> #include <unistd.h> #include <stdlib.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <pthread.h> #include <semaphore.h> #includ…...

编程日记 2025/5/14 21:12:25

定制化APP：开启企业数字化转型新未来

在当今快速发展的数字时代，企业的生存与发展不仅依赖于其传统的运营模式，更需要借助创新的技术手段来提升效率、优化服务并创造价值。而定制化的移动应用程序（简称“定制化APP”）正是实现这一目标的重要工具之一。通过量身定制的应用程序，企业能够更好地满足自身独特的业务…...

编程日记 2025/5/16 17:40:29

JS宏进阶：XMLHttpRequest对象

一、概述 XMLHttpRequest简称XHR，它是一个可以在JavaScript中使用的对象，用于在后台与服务器交换数据，实现页面的局部更新，而无需重新加载整个页面，也是Ajax（Asynchronous JavaScript and XML）…...

编程日记 2025/5/18 22:57:05

点大商城V2-2.6.6源码全开源uniapp +搭建教程

一.介绍点大商城V2独立开源版本，版本更新至2.6.6，系统支持多端，前端为UNiapp，多端编译。二.搭建环境： 系统环境：CentOS、运行环境：宝塔 Linux 网站环境：Nginx 1.21 MySQL 5.…...

编程日记 2025/5/19 5:11:01

Docker的深入浅出

目录 Docker引擎 Docker镜像 (镜像由多个层组成，每层叠加之后，从外部看来就如一个独立的对象。镜像内部是一个精简的操作系统（OS），同时还包含应用运行所必须的文件和依赖包) Docker容器应用容器化--Docker化最佳…...

编程日记 2025/5/19 1:19:49

文章目录

1. 题目来源

2. 题目解析

相关文章：