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

面试算法30:插入、删除和随机访问都是O(1)的容器

题目

设计一个数据结构,使如下3个操作的时间复杂度都是O(1)。

  • insert(value):如果数据集中不包含一个数值,则把它添加到数据集中。
  • remove(value):如果数据集中包含一个数值,则把它删除。
  • getRandom():随机返回数据集中的一个数值,要求数据集中每个数字被返回的概率都相同。

分析

由于题目要求插入和删除(包括判断数据集中是否包含一个数值)的时间复杂度都是O(1),能够同时满足这些时间效率要求的只有哈希表,因此这个数据结构要用到哈希表。但是如果只用哈希表,则不能等概率地返回其中的每个数值。

如果数值是保存在数组中的,那么很容易实现等概率返回数组中的每个数值。假设数组的长度是n,那么等概率随机生成从0到n-1的一个数字。如果生成的随机数是i,则返回数组中下标为i的数值。由此可以发现,需要结合哈希表和数组的特性来设计这个数据容器。

由于数值保存在数组中,因此需要知道每个数值在数组中的位置,否则在删除的时候就必须顺序扫描整个数组才能找到待删除的数值,那就需要O(n)的时间。通常把每个数值在数组中的位置信息保存到一个HashMap中,HashMap的键是数值,而对应的值为它在数组中的位置。

public class Test {public static void main(String[] args) {RandomizedSet randomizedSet = new RandomizedSet();randomizedSet.insert(1);randomizedSet.insert(2);randomizedSet.insert(3);randomizedSet.insert(4);for (int i = 0; i < randomizedSet.nums.size(); i++) {System.out.println(randomizedSet.nums.get(i));}System.out.println("-----------------------");randomizedSet.remove(2);for (int i = 0; i < randomizedSet.nums.size(); i++) {System.out.println(randomizedSet.nums.get(i));}System.out.println("-----------------------");System.out.println(randomizedSet.getRandom());}static class RandomizedSet {HashMap<Integer, Integer> numToLocation;ArrayList<Integer> nums;public RandomizedSet() {numToLocation = new HashMap<>();nums = new ArrayList<>();}public boolean insert(int val) {if (numToLocation.containsKey(val)) {return false;}numToLocation.put(val, nums.size());nums.add(val);return true;}public boolean remove(int val) {if (!numToLocation.containsKey(val)) {return false;}int location = numToLocation.get(val);numToLocation.put(nums.get(nums.size() - 1), location);numToLocation.remove(val);nums.set(location, nums.get(nums.size() - 1));nums.remove(nums.size() - 1);return true;}public int getRandom() {Random random = new Random();int r = random.nextInt(nums.size());return nums.get(r);}}
}

相关文章:

面试算法30:插入、删除和随机访问都是O(1)的容器

题目 设计一个数据结构&#xff0c;使如下3个操作的时间复杂度都是O&#xff08;1&#xff09;。 insert&#xff08;value&#xff09;&#xff1a;如果数据集中不包含一个数值&#xff0c;则把它添加到数据集中。remove&#xff08;value&#xff09;&#xff1a;如果数据集…...

Qt/C++开源作品45-CPU内存显示控件/和任务管理器一致

一、前言 在很多软件上&#xff0c;会在某个部位显示一个部件&#xff0c;专门显示当前的CPU使用率以及内存占用&#xff0c;方便用户判断当前程序或者当前环境中是否还有剩余的CPU和内存留给程序使用&#xff0c;在不用打开任务管理器或者资源查看器的时候直接得知当前系统的…...

win32汇编-使用子程序

当程序中相同功能的一段代码用得比较频繁时&#xff0c;可以将它分离出来写成一个子程序&#xff0c;在主程序中用call指令来调用它。这样可以不用重复写相同的代码&#xff0c; 仅仅用call指令就可以完成多次同样的工作了。Win 32汇编中的子程序也采用堆栈来传递参数&#xff…...

【论文阅读】 Cola-Dif; An explainable task-specific synthesis network

文章目录 CoLa-Diff: Conditional Latent Diffusion Model for Multi-modal MRI SynthesisAn Explainable Deep Framework: Towards Task-Specific Fusion for Multi-to-One MRI Synthesis CoLa-Diff: Conditional Latent Diffusion Model for Multi-modal MRI Synthesis 论文…...

ShareMouse for Mac(多台电脑鼠标键盘共享软件)

ShareMouse mac版是一款Mac平台上可以在多台电脑间共享鼠标的工具软件&#xff0c;sharemousefor Mac支持 Windows 与 Mac&#xff0c;并可以在不同电脑间共享剪贴板。只需要移动鼠标指针的到想控制的显示器那里去、鼠标光标就会神奇地“跨越”到邻近的电脑屏幕上。每个计算机都…...

中文编程开发语言工具开发案例:多种称重方式编程实际例子

中文编程开发语言工具开发案例&#xff1a;多种称重方式编程实际例子 上图为 计价秤&#xff0c;使用串口通讯线连接电脑的主机&#xff0c;软件自动读取称的重量&#xff0c;自动计算金额。这种方式称重快速&#xff0c;不需再打印条码。 上图这个称重方式为 一体称称重&#…...

国密sm2的Vue、Python、Java互通使用

目录 一、Vue 二、Python 三、Java 一、Vue # npm install --save sm-cryptoimport {sm2} from sm-crypto const cipherMode 1 const private_key d9d37f4f46e8514c6f9398a984e74f3eead994e8f4ac5f92e5deb313cb5ad6a6 const public_key 04 e332ee43ac37be458550652fb9…...

如何通过SK集成chatGPT实现DotNet项目工程化?

智能助手服务 以下案例将讲解如何实现天气插件 当前文档对应src/assistant/Chat.SemanticServer项目 首先我们介绍一下Chat.SemanticServer的技术架构 SemanticKernel 是什么&#xff1f; Semantic Kernel是一个SDK&#xff0c;它将OpenAI、Azure OpenAI和Hugging Face等大…...

DRM中render-node编号的分配

DRM系统 DRM是direct rendering manager的简称。DRM是linux kernel中与负责video cards功能的GPU打交道的子系统。DRM给出了一组API&#xff0c;可以供用户程序来发送命令和数据给GPU设备从而来控制比如display、render等功能。 render-node由来 在以前&#xff0c;DRM子系统…...

将输入对象转换为数组数组的维度大于等于1numpy.atleast_1d()

【小白从小学Python、C、Java】 【计算机等考500强证书考研】 【Python-数据分析】 将输入对象转换为数组 数组的维度大于等于1 numpy.atleast_1d() 选择题 使用numpy.atleast_1d()函数,下列正确的是&#xff1f; import numpy as np a1 1 a2 ((1,2,3),(4,5,6)) print("…...

js 删除树状图无用数据,如果子级没有数据则删除

有一个需求&#xff0c;当你从后端拿到一个树状图的时候&#xff0c;有些子级没数据&#xff0c;这时就需要我们处理一下数据&#xff0c;当然了&#xff0c;如果第一层底下的第二层没数据&#xff0c;第二层底下的所有都没数据&#xff0c;那这一层都不需要。 我的写法&#x…...

Docker 容器化(初学者的分享)

目录 一、什么是docker 二、docker的缺陷 三、简单的操作 一、首先配置一台虚拟机 二、安装Docker-CE 一、安装utils 二、 将 Docker 的软件源添加到 CentOS 的 yum 仓库中。这样可以通过 yum 命令来安装、更新和管理 Docker 相关的软件包。 三、将 download.docker.co…...

LCS 01.下载插件

​​题目来源&#xff1a; leetcode题目&#xff0c;网址&#xff1a;写文章-CSDN创作中心 解题思路&#xff1a; 假设需要 n 分钟下载插件&#xff0c;前 n-1 分钟将带宽加倍&#xff0c;最后一分钟下载时总时间最少。 解题代码&#xff1a; class Solution { public:int l…...

架构-设计原则

1、面向对象的SOLID 1.1 概述 SOLID是5个设计原则开头字母的缩写&#xff0c;其本身就有“稳定的”的意思&#xff0c;寓意是“遵从SOLID原则可以建立稳定、灵活、健壮的系统”。5个原则分别如下&#xff1a; Single Responsibility Principle&#xff08;SRP&#xff09;&am…...

在 Python 3 中释放 LightGBM 的力量:您的机器学习大师之路

机器学习是 Python 占据主导地位的领域,它一直在给全球各行各业带来革命性的变化。要在这个不断变化的环境中脱颖而出,掌握正确的工具是关键。LightGBM 就是这样一个工具,它是一个强大且快速的梯度提升框架。在这份综合指南中,我们将通过实际示例和示例数据集从基础知识到高…...

Spring学习笔记(2)

Spring学习笔记&#xff08;2&#xff09; 一、Spring配置非定义Bean1.1 DruidDataSource1.2、Connection1.3、Date1.4、SqlSessionFactory 二、Bean实例化的基本流程2.1 BeanDefinition2.2 单例池和流程总结 三、Spring的bean工厂后处理器3.1 bean工厂后处理器入门3.2、注册Be…...

cmd使用ssh连接Linux脚本

前言 在开发过程中&#xff0c;由于MobaXterm&#xff0c;我不知道怎么分页&#xff08;不是屏内分页&#xff09;&#xff0c;用crtlTab&#xff0c;用起来不习惯&#xff0c;主要是MobaXterm连接了多个服务器&#xff0c;切换起来很麻烦。我是比较习惯使用altTab&#xff0c…...

Python万圣节蝙蝠

目录 系列文章 前言 蝙蝠 程序设计 程序分析 运行结果 尾声 系列文章 序号文章目录直达链接1浪漫520表白代码https://want595.blog.csdn.net/article/details/1306668812满屏表白代码https://want595.blog.csdn.net/article/details/1297945183跳动的爱心https://want5…...

TCP流套接字编程

文章目录 前言TCP 和 UDP 的特点对比TcpEchoServer 服务端实现1. 创建 ServerSocket 类实现通信双方建立连接2. 取出建立的连接实现双方通信3. 服务端业务逻辑实现关闭资源服务端整体代码 TcpEchoClient 客户端实现1. 创建出 Socket 对象来与服务端实现通信2. 实现客户端的主要…...

Python迭代器创建与使用:从入门到精通

一、可迭代对象 1、 什么是可迭代对象&#xff1f; 表示可以逐一迭代或者遍历的对象&#xff0c;序列&#xff1a;列表、元组、集合、字符串。非序列&#xff1a;字典、文件。自定义对象&#xff1a;实现了__iter__()方法的对象&#xff1b;实现了使用整数索引的 getitem()方…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...