想要精通算法和SQL的成长之路 - 存在重复元素
想要精通算法和SQL的成长之路 - 存在重复元素
- 前言
- 一. 存在重复元素II
- 二. 存在重复元素III
- 2.1 基于红黑树增删改查
前言
想要精通算法和SQL的成长之路 - 系列导航
一. 存在重复元素II
原题链接
思路:
- 我们用
HashSet
存储元素,做到去重的效果。同时存储的元素个数,固定在k个。这个HashSet
相当于是一个滑动窗口了。 - 那么从左往右遍历,不断地往
HashSet
中塞元素,一旦超过容量,剔除滑动窗口最左侧元素。set.remove(nums[i - k - 1]);
- 遍历过程中,一旦发现当前元素存在于
HashSet
中,直接返回true
即可。
代码如下:
public boolean containsNearbyDuplicate(int[] nums, int k) {HashSet<Integer> set = new HashSet<>();for (int i = 0; i < nums.length; i++) {// 滑动窗口只存储k个元素,超过了,则移除if (i > k) {set.remove(nums[i - k - 1]);}if (set.contains(nums[i])) {return true;}set.add(nums[i]);}return false;
}
二. 存在重复元素III
原题链接
我们先来一个最简单的思路,暴力法:
- 针对每个元素,作为滑动窗口的左边界。往后固定
indexDiff
长度的区间。 - 我们在
[left,left+indexDiff]
区间内遍历数组,计算差值。如果满足差值 <valueDiff
值,说明找到满足条件的结果,返回true
。
但是,这种操作,有着大量的重复计算,而且数组的无规律性,在最坏的情况下,我们得遍历整个长度为 k
的区间数组。那咋办呢?
思路如下:
- 我们可以维护一个有序并且长度为
k
的滑动窗口。那么对于该区间的任意一个数字num
。既然要满足差值 <valueDiff
值。那么在这个有序的集合当中。哪个数字最满足条件? - 第一种:小于等于
num
的最大值。第二种:和大于等于num
的最小值。即值num
左右两侧最靠近的数值是我们想要的。 - 那么对于有序的数组而言,想要查找上面两个数,用哪种方式最合适?二分法。
- 当然,我们还需要不断地维护这个滑动窗口对应的数据结构。
2.1 基于红黑树增删改查
下面来自百度百科的相关红黑树介绍:
- 红黑树是一种特化的AVL树(平衡二叉树),都是在进行插入和删除操作时通过若干次特定操作保持二叉查找树的平衡,从而获得较高的查找性能。
- 而这个特定操作,对于红黑树而言,可以限制到最多三次。
- 它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在
O(log n)
时间内做查找,插入和删除,这里的n
是树中元素的数目。
针对上面的功能,红黑树都具备其查询:
- 查询不超过
num
的最大值:floor
函数。注意:如果找不到则返回null
。 - 查询超过
num
的最小值:ceiling
函数。注意:如果找不到则返回null
。
那么我们就不难写出代码:切记,对象和基本数据类型的比较,要判断null
,否则会报空指针哦~
// floorNum <= num ,最大值
Long floorNum = tree.floor(num);
// ceilingNum >=num ,最小值
Long ceilingNum = tree.ceiling(num);
if (floorNum != null && num - floorNum <= valueDiff) {return true;
}
if (ceilingNum != null && ceilingNum - num <= valueDiff) {return true;
}
由于题目的元素值存在以下范围:
因此我们在存储的时候,要把它转成Long
型。最终代码如下:
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {TreeSet<Long> tree = new TreeSet<>();for (int i = 0; i < nums.length; i++) {// int 转 long,因为限制问题long num = nums[i] * 1L;// floorNum <= num ,最大值Long floorNum = tree.floor(num);// ceilingNum >=num ,最小值Long ceilingNum = tree.ceiling(num);if (floorNum != null && num - floorNum <= valueDiff) {return true;}if (ceilingNum != null && ceilingNum - num <= valueDiff) {return true;}tree.add(num);// 超过了滑动窗口大小if (i >= indexDiff) {tree.remove(nums[i - indexDiff] * 1L);}}return false;
}
相关文章:

想要精通算法和SQL的成长之路 - 存在重复元素
想要精通算法和SQL的成长之路 - 存在重复元素 前言一. 存在重复元素II二. 存在重复元素III2.1 基于红黑树增删改查 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 存在重复元素II 原题链接 思路: 我们用HashSet存储元素,做到去重的效果。同时存储…...

使用华为eNSP组网试验⑸-访问控制
今天练习使用华为sNSP模拟网络设备上的访问控制,这样的操作我经常在华为的S7706、S5720、S5735或者H3C的S5500、S5130、S7706上进行,在网络设备上根据情况应用访问控制的策略是一个网管必须熟练的操作,只是在真机上操作一般比较谨慎ÿ…...

iPhone苹果手机闹钟智能跳过节假日怎么设置?
国内绝大多数的手机用户使用的操作系统只有三个,安卓、鸿蒙和苹果的ios。而iPhone苹果手机的忠实用户是非常多的,所以日积月累中用户数量也就非常庞大,并且相当一部分用户都是上班族。而工作忙碌的上班族因为事情比较多,为了避免自…...

TenDB Cluster 简介
文章目录 1.简介2.TSpider3.TenDB4.Tdbctl5.TenDB Cluster Operator参考文献 1.简介 TenDB Cluster 是腾讯游戏 CROS DBA 团队提供的 MySQL 分布式关系型数据库解决方案。主要特点包括:透明分库分表、高可用的 MySQL 集群服务,透明及在线的扩容及缩容&a…...

【刷题笔记10.6】LeetCode:翻转二叉树
LeetCode:翻转二叉树 一、题目描述 给你一颗二叉树的根节点root,翻转这颗二叉树,并返回其根节点。 二、分析 我们在做二叉树题目时候,第一想到的应该是用 递归 来解决。 仔细看下题目的 输入 和 输出,输出的左右…...

【高阶数据结构】图详解第一篇:图的基本概念及其存储结构(邻接矩阵和邻接表)
文章目录 1. 图的基本概念1.1 什么是图1.2 有向图和无向图1.3 完全图1.4 邻接顶点1.5 顶点的度1.6 路径1.7 路径长度1.8 简单路径与回路1.9 子图1.10 连通图1.11 强连通图1.12 生成树 2. 图的存储结构2.1 邻接矩阵2.2 邻接矩阵代码实现结构定义构造函数添加边打印图测试 2.3 邻…...
IPV4跟IPV6的区别
如今互联网快速发展ipv4已经满足不了现在的需求,那么这时候就需要用更大的地址空间来代替,这时候ipv6就可以满足这一需求,相比ipv4它有更大的地址空间可供使用。下面我将分享一下有何区别。 IPv4与IPv6之间的区别: 1、地址长度的区别:IPv4具…...

利用fitnesse实现api接口自动化测试
上午在园子里乱逛,看了不少小伙伴们分享的接口测试方面的知识,仔细想想,我做接口测试也有几个年头了,大家所叙述到的一些经验或多或少,我也曾遇到过,突然意识到知识的点滴积累是多么的重要,我记…...
【LeetCode】1154.一年中的第几天
题目描述: 给你一个字符串 date ,按 YYYY-MM-DD 格式表示一个 现行公元纪年法 日期。返回该日期是当年的第几天。 示例 1: 输入:date "2019-01-09" 输出:9 解释:给定日期是2019年的第九天。示…...

4.物联网射频识别,RFID开发【智能门禁项目】
补充:学习路径 一。项目介绍及需求分析 1.酒店智能门禁使用场景介绍 1.客人入住 客人在前台办理入住手续,前台管理员通过门禁管理系统为客户开一张门禁卡 客户持卡到相应客房,用IC 卡刷卡开门 客人过了入住时间后,卡自动失效&a…...
CompletableFuture 和 Future 的选择,以及CompletableFuture的用法
在 Java 编程中,异步编程是一种重要的技术,它允许你在执行长时间运行的任务时不会阻塞主线程。为了支持异步编程,Java 提供了 Future 和 CompletableFuture 这两个关键的类。在本文中,我们将比较它们的特点、优缺点以及使用场景。…...
美国第三大财产和意外险公司利宝保险集团利用 OpenText EnCase 取证收集技术控制法律风险和成本
美国第三大财产和意外险公司利宝保险集团利用 OpenText EnCase 取证收集技术控制法律风险和成本 利宝保险集团通过内部取证收集技术控制法律风险和成本。OpenText EnCase Information Assurance(以前称为 EnCase eDiscovery)使保险公司巨头能够自信高效地…...

打包报错JavaScript heap out of memory
npm run build 的时候出现了Reached heap limit Allocation failed - JavaScript heap out of memory,报错信息如下图所示。 奇怪的时候这个报错信息在本地不会出现,通过jekins在服务器打包部署的时候才会出现。于是进入服务器执行下面一句代码ÿ…...

Android Camera FW 里的requestId和frameId
安卓相机frameworks里面经常出现requestId和frameId,最近简单看了一下代码,发现相关流程还是很复杂的,总结来看requestId 就是上层(java)发送的repeating(capture)请求的id,是从0开始递增的。 这是CameraD…...
代理IP与Socks5代理在技术世界的多元应用
在数字化时代,网络工程师的任务不仅是维护网络的稳定性,还需要应对各种技术挑战。代理IP与Socks5代理作为技术工具箱中的两把利器,在跨界电商、爬虫、出海业务、网络安全和游戏领域中发挥了关键作用。本文将深入探讨这两项技术在不同领域的多…...

计算机专业毕业设计项目推荐12-志愿者管理系统(Spring+Js+Mysql)
志愿者管理系统(SpringJsMysql) **介绍****各部分模块实现** 介绍 本系列(后期可能博主会统一为专栏)博文献给即将毕业的计算机专业同学们,因为博主自身本科和硕士也是科班出生,所以也比较了解计算机专业的毕业设计流程以及模式,在编写的过程…...

苹果文件传到mac电脑用什么软件?
在数字化时代,文件传输已经成为我们日常生活中不可或缺的一部分。然而,苹果用户在将手机文件传输到电脑时,往往会面临一些困扰。曾经的“文件传输助手”并不能完全满足用户的需求。于是,很多人开始寻找更便捷的解决方案。在本文中…...

深入理解Docker:简化部署与管理的利器
文章目录 引言Docker简介Docker的背景和发展Docker的优势和特点 Docker的基本概念和架构镜像(Image)容器(Container)仓库(Repository)Docker架构 Docker的常用命令和操作Docker的安装和配置Docker镜像的管理…...

软考对找工作有用吗?
软考是指软件技术专业资格考试,是由中国人力资源和社会保障部主管的一项国家级考试。软考的目标是评估和认证软件技术人员的专业能力,提高软件行业的整体素质和竞争力。那么,软考对找工作有用吗?本文将从以下几个方面进行分析。 首…...

Android系统启动之init进程启动+Zygote进程启动分析
一、基础概念理解 init进程 Android系统所有进程的祖先,是Android系统内核初始化完毕后,进入用户空间启动的第一个进程。 Android虚拟机 Dalvik虚拟机是谷歌自己设计的用于Android平台的虚拟机。Android4.4同时提供了Dalvik和ART虚拟机。Android5.0以后…...

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

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...

家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...