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

想要精通算法和SQL的成长之路 - 存在重复元素

想要精通算法和SQL的成长之路 - 存在重复元素

  • 前言
  • 一. 存在重复元素II
  • 二. 存在重复元素III
    • 2.1 基于红黑树增删改查

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 存在重复元素II

原题链接
在这里插入图片描述

思路:

  1. 我们用HashSet存储元素,做到去重的效果。同时存储的元素个数,固定在k个。这个HashSet相当于是一个滑动窗口了。
  2. 那么从左往右遍历,不断地往HashSet中塞元素,一旦超过容量,剔除滑动窗口最左侧元素。set.remove(nums[i - k - 1]);
  3. 遍历过程中,一旦发现当前元素存在于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

原题链接
在这里插入图片描述
我们先来一个最简单的思路,暴力法:

  1. 针对每个元素,作为滑动窗口的左边界。往后固定indexDiff长度的区间。
  2. 我们在[left,left+indexDiff] 区间内遍历数组,计算差值。如果满足差值 < valueDiff 值,说明找到满足条件的结果,返回true

但是,这种操作,有着大量的重复计算,而且数组的无规律性,在最坏的情况下,我们得遍历整个长度为 k 的区间数组。那咋办呢?

思路如下:

  1. 我们可以维护一个有序并且长度为 k 的滑动窗口。那么对于该区间的任意一个数字num。既然要满足差值 < valueDiff 值。那么在这个有序的集合当中。哪个数字最满足条件?
  2. 第一种:小于等于 num 的最大值。第二种:和大于等于num的最小值即值num左右两侧最靠近的数值是我们想要的。
  3. 那么对于有序的数组而言,想要查找上面两个数,用哪种方式最合适?二分法。
  4. 当然,我们还需要不断地维护这个滑动窗口对应的数据结构。

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 原题链接 思路&#xff1a; 我们用HashSet存储元素&#xff0c;做到去重的效果。同时存储…...

使用华为eNSP组网试验⑸-访问控制

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

iPhone苹果手机闹钟智能跳过节假日怎么设置?

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

TenDB Cluster 简介

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

【刷题笔记10.6】LeetCode:翻转二叉树

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

【高阶数据结构】图详解第一篇:图的基本概念及其存储结构(邻接矩阵和邻接表)

文章目录 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已经满足不了现在的需求&#xff0c;那么这时候就需要用更大的地址空间来代替&#xff0c;这时候ipv6就可以满足这一需求&#xff0c;相比ipv4它有更大的地址空间可供使用。下面我将分享一下有何区别。 IPv4与IPv6之间的区别: 1、地址长度的区别:IPv4具…...

利用fitnesse实现api接口自动化测试

上午在园子里乱逛&#xff0c;看了不少小伙伴们分享的接口测试方面的知识&#xff0c;仔细想想&#xff0c;我做接口测试也有几个年头了&#xff0c;大家所叙述到的一些经验或多或少&#xff0c;我也曾遇到过&#xff0c;突然意识到知识的点滴积累是多么的重要&#xff0c;我记…...

【LeetCode】1154.一年中的第几天

题目描述&#xff1a; 给你一个字符串 date &#xff0c;按 YYYY-MM-DD 格式表示一个 现行公元纪年法 日期。返回该日期是当年的第几天。 示例 1&#xff1a; 输入&#xff1a;date "2019-01-09" 输出&#xff1a;9 解释&#xff1a;给定日期是2019年的第九天。示…...

4.物联网射频识别,RFID开发【智能门禁项目】

补充&#xff1a;学习路径 一。项目介绍及需求分析 1.酒店智能门禁使用场景介绍 1.客人入住 客人在前台办理入住手续&#xff0c;前台管理员通过门禁管理系统为客户开一张门禁卡 客户持卡到相应客房&#xff0c;用IC 卡刷卡开门 客人过了入住时间后&#xff0c;卡自动失效&a…...

CompletableFuture 和 Future 的选择,以及CompletableFuture的用法

在 Java 编程中&#xff0c;异步编程是一种重要的技术&#xff0c;它允许你在执行长时间运行的任务时不会阻塞主线程。为了支持异步编程&#xff0c;Java 提供了 Future 和 CompletableFuture 这两个关键的类。在本文中&#xff0c;我们将比较它们的特点、优缺点以及使用场景。…...

美国第三大财产和意外险公司利宝保险集团利用 OpenText EnCase 取证收集技术控制法律风险和成本

美国第三大财产和意外险公司利宝保险集团利用 OpenText EnCase 取证收集技术控制法律风险和成本 利宝保险集团通过内部取证收集技术控制法律风险和成本。OpenText EnCase Information Assurance&#xff08;以前称为 EnCase eDiscovery&#xff09;使保险公司巨头能够自信高效地…...

打包报错JavaScript heap out of memory

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

Android Camera FW 里的requestId和frameId

安卓相机frameworks里面经常出现requestId和frameId&#xff0c;最近简单看了一下代码&#xff0c;发现相关流程还是很复杂的&#xff0c;总结来看requestId 就是上层&#xff08;java&#xff09;发送的repeating(capture)请求的id&#xff0c;是从0开始递增的。 这是CameraD…...

代理IP与Socks5代理在技术世界的多元应用

在数字化时代&#xff0c;网络工程师的任务不仅是维护网络的稳定性&#xff0c;还需要应对各种技术挑战。代理IP与Socks5代理作为技术工具箱中的两把利器&#xff0c;在跨界电商、爬虫、出海业务、网络安全和游戏领域中发挥了关键作用。本文将深入探讨这两项技术在不同领域的多…...

计算机专业毕业设计项目推荐12-志愿者管理系统(Spring+Js+Mysql)

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

苹果文件传到mac电脑用什么软件?

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

深入理解Docker:简化部署与管理的利器

文章目录 引言Docker简介Docker的背景和发展Docker的优势和特点 Docker的基本概念和架构镜像&#xff08;Image&#xff09;容器&#xff08;Container&#xff09;仓库&#xff08;Repository&#xff09;Docker架构 Docker的常用命令和操作Docker的安装和配置Docker镜像的管理…...

软考对找工作有用吗?

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

Android系统启动之init进程启动+Zygote进程启动分析

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

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...