哈希表的介绍
1.哈希表的介绍
在哈希表中插入、删除或查找一个元素都只需要O(1)的时间,因此经常被用来优化时间效率。
在Java中,哈希表有两个对应的类型,即HashSet和HashMap。
2.HashSet的应用
若每个元素都只有一个值,则用HashSet,如,HashSet在图搜索时经常用来存储已经搜索过的节点。
以下为HashSet的常用函数:
函数 | 功能 |
---|---|
add | 添加一个元素 |
contains | 判断是否包含一个元素 |
remove | 删除一个元素 |
size | 返回元素的数目 |
3.HashMap的应用
若每个元素都存在一个值到另外一个值的映射,那么就用HashMap。
以下为HashMap的常用函数:
函数 | 功能 |
---|---|
containsKey | 判断HashMap中是否包括某个键 |
get | 返回键对应的值,否则null |
getOrDefault | 返回键对应的值,否则返回输入的默认值 |
put | 添加一组映射,否则修改键对应的值 |
putIfAbsent | 当键不存在时,添加一组映射 |
remove | 删除某个键 |
replace | 修改某个键对应的值 |
size | 返回映射数目 |
可以基于数组实现哈希表。
4.题目
面试30-插入、删除和随机访问都是O(1)的容器
解题思路:
需要结合哈希表和数组的特性来设计数据容器。
采用长度可变的数组:
ArrayList list = new ArrayList();
其中删除操作若考虑O(1)的时间复杂度,因为不能保证删除的元素总在末尾,所以,将末尾的元素与要删除的元素换位置(单方面交换–看代码),然后删除末尾的元素,注意,都是从0开始。
提交的代码:
class RandomizedSet {HashMap<Integer,Integer> map;//定义哈希表ArrayList<Integer> nums;//定义长度可变的数组//初始化public RandomizedSet(){map=new HashMap<>();nums=new ArrayList<>();}//插入public boolean insert(int val){if(map.containsKey(val)){return false;}map.put(val,nums.size());nums.add(val);return true;}//删除public boolean remove(int val){if(!map.containsKey(val)){return false;}int loc=map.get(val);map.put(nums.get(nums.size()-1),loc);//数组中最后一个元素放在要删除的位置map.remove(val);//map中删除val对应的键值对nums.set(loc,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());//随机生成0-nums.size()-1中的数字return nums.get(r);}
}
ArrayList的用法
相关文章:

哈希表的介绍
1.哈希表的介绍 在哈希表中插入、删除或查找一个元素都只需要O(1)的时间,因此经常被用来优化时间效率。 在Java中,哈希表有两个对应的类型,即HashSet和HashMap。 2.HashSet的应用 若每个元素都只有一个值,则用HashSet…...

spring cloud gateway 实现redis动态路由及自动项目路由上报
前言 spring cloud gateway默认为内存存储策略,通过配置文件加载的方式生成路由定义信息 可以看到,RouteDefinitionRepository继承了两个父接口,分别为RouteDefinitionLocator和RouteDefinitionWriter,RouteDefinitionLocator定…...

c++函数对象(仿函数)、谓词、内建函数对象
1、函数对象 1.1 概念 重载函数调用操作符的类,这个类的对象就是函数对象,在使用这个函数对象对应使用重载的()符号时,行为类似于函数调用,因此这个函数也叫仿函数。 注意:函数对象࿰…...

物联网对供应链管理的影响
物联网对于许多行业来说都是一项革命性技术,其应用领域涉及零售、交通、金融、医疗保健和能源等行业。物联网在供应链等流程中已经展示了其深度的潜力。管理、预测和监督应用程序有助于车队运输经理提高配送的运营效率,并增加决策的准确性。如今…...

c++ 那些事 笔记
GitHub - Light-City/CPlusPlusThings: C那些事 1. ① extern extern关键字,C语言extern关键字用法详解 如果全局变量不在文件的开头定义,其有效的作用范围只限于其定义处到文件结束。如果在定义点之前的函数想引用该全局变量,则应该在…...

心跳机制Redis
进入命令传播阶段候,master与slave间需要进行信息交换,使用心跳机制进行维护,实现双方连接保持在线 master心跳: 指令:PING 周期:由repl-ping-slave-period决定,默认10秒 作用&#…...
蓝桥杯算法训练合集十七 1.数字反转2.试题39713.矮人采金子4.筛法5.机器指令
目录 1.数字反转 2.试题3971 3.矮人采金子 4.筛法 5.机器指令 1.数字反转 问题描述 给定一个整数,请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式,即除非给定的原数为零,否则反转后得到的新数的最高位数字不应为零&…...

第一章 初识 Spring Security
第一章 初识 Spring Security 1、权限管理 权限管理 基本上涉及到用户参与的系统都要进行权限管理,权限管理属于系统安全的范畴,权限管理实现了对用户访问系统的控制,按照安全规则或者安全策略控制用户可以访问而且只能访问自己被授权的资…...
2023-02-20 关于回朔的思考
摘要: 考虑命运来回动荡交织,一些新的规划在不断的扩充, 而一些历史则开始陷入回朔。 有必要对历史和过往做一些规划和思考。 需要注意在这个阶段, 第一优先级是在反刍中将其最大化。 理论层: 一. 数据库的基础理论 ANSI SQL到词法解析和语法解析mysql的SQL层对…...

推荐系统[八]算法实践总结V1:淘宝逛逛and阿里飞猪个性化推荐:召回算法实践总结【冷启动召回、复购召回、用户行为召回等算法实战】
0.前言:召回排序流程策略算法简介 推荐可分为以下四个流程,分别是召回、粗排、精排以及重排: 召回是源头,在某种意义上决定着整个推荐的天花板;粗排是初筛,一般不会上复杂模型;精排是整个推荐环节的重中之重,在特征和模型上都会做的比较复杂;重排,一般是做打散或满足…...

适合初学者的超详细实用调试技巧(下)
我们日常写代码的时候,常常会遇到bug的情况,这个时候像我这样的初学者就会像无头苍蝇一样这里改改那里删删,调试的重要性也就显现出来,这篇文章接着上文来讲解。 上文地址:(8条消息) 适合初学者的超详细实用调试技巧&…...

C# String与StringBuilder 的区分
重点 1)它是比较的栈里面的值是否相等(值比较) 2)Equals它比较的是堆里面的值是否相等(引用地址值比较) 3)Object.ReferenceEquals(obj1,obj2)它是比较的是内存地址是否相等 问题描述: 今日提交代码时候,被检测工具发出修改建议。遂补充一下知识 1.什么…...
【麒麟】基于GPS北斗卫星技术的NTP网络时间服务器
【麒麟】基于GPS北斗卫星技术的NTP网络时间服务器 【麒麟】基于GPS北斗卫星技术的NTP网络时间服务器 麒麟系统NTP授时方案 设计思路: 在通用的麒麟服务器内部固定一块北斗卫星接收模块并引出卫星天线接口,卫星模块接收北斗卫星数据并解码输出时间数据&…...
“互联网+”下劳动关系认定的现状
1. 劳动关系的认定标准。依据目前我国法律的有关规定, 判定劳动关系存在两种情况:其一, 在有书面劳动合同的情况下, 这时应以书面合同作为认定标准;其二, 在没有书面合同的情况下, 则依据2005年劳社部的《关于确立劳动关系有关事项的通知》来认定, 其中第一条:“用人单位招用劳…...

LPWAN及高效弹性工业物联网核心技术方案
20多年前的一辆拖拉机就是一个纯机械的产品,里面可能并没有电子或者软件的构成;而随后随着软件的发展,拖拉机中嵌入了软件,它能控制发动机的功率及拖拉机防抱死系统;接下来,通过融入各种软件,拖…...
OPTIONS FMTSEARCH
FMTSEARCH 指定要检索的格式目录列表,语法如下:OPTIONS FMTSEARCH(catalog-specification-1<catalog-specification-2 … >);使用PROC FORMAT时可以定义格式目录,LIBRARYlibref或LIBRARYlibref.catalog。格式目录可以是libref或libref.…...

Python3 pip
Python3 pip pip 是 Python 包管理工具,该工具提供了对 Python 包的查找、下载、安装、卸载的功能。 软件包也可以在 https://pypi.org/ 中找到。 目前最新的 Python 版本已经预装了 pip。 注意:Python 2.7.9 或 Python 3.4 以上版本都自带 pip 工具…...

【2023-02-20】JS逆向之翼支付
提示:文章仅供参考,禁止用于非法途径 文章目录前言分析总结前言 真的好久没更了…… 提示:以下是本篇文章正文内容,下面案例可供参考 分析 进到网页,加载两个接口 applyLoginFactor 接口返回一个RSA公钥࿰…...

假如面试官问你Babel的原理该怎么回答
1. 什么是 Babel 简单地说,Babel 能够转译 ECMAScript 2015 的代码,使它在旧的浏览器或者环境中也能够运行。 // es2015 的 const 和 arrow function const add (a, b) > a b;// Babel 转译后 var add function add(a, b) {return a b; };Babel…...

深入Spring底层透析Bean创建过程之拨云见日篇
目录前言一.BeanFactory快速入门1. BeanFactory创建Bean2. BeanFactory和ApplicationContext的关系3. 和ApplicationContext区别(高频问点)4. BeanFactory的继承体系5. ApplicationContext的继承体系二.Bean实例化的基本流程(重点)前言 首先感谢您的阅览࿰…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...

TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...

【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...

云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...