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

算法:删除有序数组中的重复项---双指针[3]

在这里插入图片描述


1、题目:

对给定的有序数组 nums 删除重复元素,在删除重复元素之后,每个元素只出现一次,并返回新的长度,上述操作必须通过原地修改数组的方法,使用 O(1) 的空间复杂度完成。


2、分析特点:

  • 题目要求:原地修改、 有序数组
  • 原地+删除 ==> 结果数组一定比原数组的长度更短 ,并且,我们可以 把结果数组直接写在原数组上
  • 有序数组 ==> 当前元素和前一个元素是相等的时候,则不需要收集, 我们需要收集的元素,是那些不会等于前一个元素的,充分利用有序的特点 ,继续往前遍历,只要不等于前一个元素,就可以收集起来,等于了就放弃,比如 2 3 3,第一个 3 作为当前元素的时候,和前一个元素不相等,可以收集起来,到了第二个 3 和前一个元素相等了,放弃收集。

3、特点:

有序数组,剔除掉相等的,拿当前位置的元素去和前一个元素比较 ,即if (nums[fast] != nums[fast - 1]); 并且 0 位置的元素早就进入结果集,需要看后面的元素是否进结果,则定义的两个指针开始判断收集的起点下标从1开始。

定义两个指针 fast 和 slow 分别为快指针和慢指针,

快指针表示遍历原数组到达的下标位置,慢指针表示结果数组的下标位置,即下一个不同元素要填入的下标位置,初始时两个指针都指向下标 1。

快指针的范围是从 1 到 最后一个元素位置;

慢指针是从 1 开始不断根据快指针满足了条件就加入收集结果(前提,0位置的元素早就进入了结果,需要看后面的元素是否进结果);


4、代码:

    public int removeDuplicates(int[] nums) {int n = nums.length;if (n == 0) {return 0;}int slow = 1;for(int fast = 1; fast < n; fast++){if (nums[fast] != nums[fast - 1]) {nums[slow] = nums[fast];++slow;}}return slow;}

5、复杂度分析:

  • 时间复杂度:O(n),其中 n 是数组的长度。快指针和慢指针最多各移动 n 次。
  • 空间复杂度:O(1)。只需要使用常数的额外空间。

6、总结:

有序数组,剔除掉相等的,拿当前位置的元素去和前一个元素比较,即if (nums[fast] != nums[fast - 1]); 并且 0 位置的元素早就进入结果集,需要看后面的元素是否进结果,则定义的两个指针开始判断收集的起点下标从1开始。




如果本文对你有帮助的话记得给一乐点个赞哦,感谢!

相关文章:

算法:删除有序数组中的重复项---双指针[3]

1、题目&#xff1a; 对给定的有序数组 nums 删除重复元素&#xff0c;在删除重复元素之后&#xff0c;每个元素只出现一次&#xff0c;并返回新的长度&#xff0c;上述操作必须通过原地修改数组的方法&#xff0c;使用 O(1) 的空间复杂度完成。 2、分析特点&#xff1a; 题目…...

AR产业变革中的“关键先生”和“关键力量”

今年6月的WWDC大会上&#xff0c;苹果发布了头显产品Vision Pro&#xff0c;苹果CEO库克形容它&#xff1a; 开启了空间计算时代。 AR产业曾红极一时&#xff0c;但因为一些技术硬伤又减弱了声量&#xff0c;整个产业在起伏中前行。必须承认&#xff0c;这次苹果发布Vision P…...

通过 Blob 对二进制流文件下载实现文件保存下载

原理&#xff1a;前端将二进制文件做转换实现下载: 请求后端接口->接收后端返回的二进制流(通过二进制流&#xff08;Blob&#xff09;下载,把后端返回的二进制文件放在 Blob 里面)->再通过file-saver插件保存 页面上使用&#xff1a; <span click"downloadFil…...

微信小程序使用lime-echart踩坑记录

一、使用echarts包 微信小程序项目使用的是uni-app&#xff0c;插件是lime-echart&#xff0c;版本一开始安装的是lime-echart-0.7.9&#xff1b;在项目分包之后&#xff0c;为了避免主包过大&#xff0c;就将这个插件也一并搬到了分包中&#xff0c;在微信开发者工具中表现出…...

Unity 编辑器资源导入处理函数 OnPostprocessTexture :深入解析与实用案例

Unity 编辑器资源导入处理函数 OnPostprocessTexture 用法 点击封面跳转下载页面 简介 在Unity中&#xff0c;我们可以使用编辑器资源导入处理函数&#xff08;OnPostprocessTexture&#xff09;来自定义处理纹理资源的导入过程。这个函数是继承自AssetPostprocessor类的&…...

stable diffusion实践操作-宽高设置以及高清修复

系列文章目录 stable diffusion实践操作 文章目录 系列文章目录前言一、SD宽高怎么设置&#xff1f;1.1 宽高历史 二、高清修复1. 文生图中的高清修复1.按钮Hires.fix2.不同放大算法对比1.第一类2.第二类3.第三类4.第四类5.第五类6.第六类7.第七类8.第八类9.第九类10.第十类11…...

利用微调的deberta-v3-large来预测情感分类

前言&#xff1a; 昨天我们讲述了怎么利用emotion数据集进行deberta-v3-large大模型的微调&#xff0c;那今天我们就来输入一些数据来测试一下&#xff0c;看看模型的准确率&#xff0c;为了方便起见&#xff0c;我直接用测试集的前十条数据 代码&#xff1a; from transfor…...

opencv旋转图像

0 、使用旋转矩阵旋转 import cv2img cv2.imread(img.jpg, 1) (h, w) img.shape[:2] # 获取图像的宽和高# 定义旋转中心坐标 center (w / 2, h / 2)# 定义旋转角度 angle 90# 定义缩放比例 scale 1# 获得旋转矩阵 M cv2.getRotationMatrix2D(center, angle, scale)# 进行…...

容器资料: Docker和Singularity

容器资料 Docker和Singularity Docker比较适合测试: 环境适配,每种环境对应一个容器。Docker需要host宿主机上运行Docker服务(root权限),隔离性很高&#xff0c;但会牺牲性能&#xff0c;对GPU环境支持不好(需要安装NVIDIAN公司的插件才能把GPU暴露给container) Sigularity可…...

如何确认linux的包管理器是yum还是apt,确认之后安装其他程序的时候就需要注意安装命令

打开终端 输入apt&#xff0c;下图中提示未找到命令&#xff0c;则基本上包管理工具就是用yum的 输入yum&#xff0c;我们看到有打印信息&#xff0c;则说明包管理工具是yum的&#xff0c;离线安装命令使用rpm...

数据分享|R语言分析上海空气质量指数数据:kmean聚类、层次聚类、时间序列分析:arima模型、指数平滑法...

全文链接&#xff1a;http://tecdat.cn/?p30131 最近我们被客户要求撰写关于上海空气质量指数的研究报告。本文向大家介绍R语言对上海PM2.5等空气质量数据&#xff08;查看文末了解数据免费获取方式&#xff09;间的相关分析和预测分析&#xff0c;主要内容包括其使用实例&…...

MySQL 8.0.34安装教程

一、下载MySQL 1.官网下载 MySQL官网下载地址&#xff1a; MySQL :: MySQL Downloads &#xff0c;选择下载社区版&#xff08;平时项目开发足够了&#xff09; 2.点击下载MySQL Installer for Windows 3.选择版本8.0.34&#xff0c;并根据自己需求&#xff0c;选择下载全社区安…...

用通俗易懂的方式讲解大模型分布式训练并行技术:概述

近年来&#xff0c;随着Transformer、MOE架构的提出&#xff0c;使得深度学习模型轻松突破上万亿规模参数&#xff0c;传统的单机单卡模式已经无法满足超大模型进行训练的要求。因此&#xff0c;我们需要基于单机多卡、甚至是多机多卡进行分布式大模型的训练。 而利用AI集群&a…...

NodeJS入门以及文件模块fs模块

NodeJS入门以及文件模块fs模块&#xff0c;本章节会详细带大家进入NodeJS开发&#xff0c;了解什么是模块化、文件系统 模块化的详解什么是模块什么是模块化ESM模块化开发CommonJS模块化操作 模块的分类内置模块 一个小知识Buffer的使用buffer常见的方法 事件监听模块events常用…...

springboot集成Elasticsearch7.16,使用https方式连接并忽略SSL证书

千万万苦利用科学上网找到了&#xff0c;记录一下 package com.warn.config.baseconfig;import co.elastic.clients.elasticsearch.ElasticsearchClient; import co.elastic.clients.json.jackson.JacksonJsonpMapper; import co.elastic.clients.transport.ElasticsearchTran…...

【已解决】pycharm 突然每次点击都开新页面,关不掉怎么办?

今天在 pycharm 中写代码&#xff0c;突然发现&#xff0c;新开的文件不再原来的页面上&#xff0c;而是新增了页面&#xff0c;导致整个屏幕全都是新开的页面&#xff0c;最难受的是&#xff0c;关不掉&#xff01; 无奈&#xff0c;我只能关闭 pycharm&#xff0c;重新双击…...

AndroidStudio最下方显示不出来Terminal等插件

File->Settings->Plugins 然后在上面的输入框中输入Terminal&#xff0c;并将最右侧的对勾打上即可。 安装即可...

python基础操作笔记

一,pickle读写json格式文件pkl k Out[15]: {k1: 2, k3: 4}with open("test822.pkl","wb") as f:pickle.dump(k,f,) with open("test822.pkl","rb") as f:kk=pickle.load(f)kk==k Out[20]: True 二、docker删除image docker rmi …...

c++ 学习 之 指针常量 和 常量指针

前言 在 C 中&#xff0c;指针常量&#xff08;constant pointer&#xff09;和常量指针&#xff08;pointer to constant&#xff09;是两种不同类型的指针&#xff0c;它们具有不同的含义和用途。 正文 指针常量&#xff08;constant pointer&#xff09;&#xff1a; 指针…...

Redis未授权访问漏洞实战

文章目录 概述Redis概述Redis 介绍Redis 简单使用Redis未授权漏洞危害 漏洞复现启动靶场环境POC漏洞验证EXP漏洞利用 总结 本次测试仅供学习使用&#xff0c;如若非法他用&#xff0c;与平台和本文作者无关&#xff0c;需自行负责&#xff01; 概述 ​ 本文章主要是针对于vulh…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

ElasticSearch搜索引擎之倒排索引及其底层算法

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

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...

libfmt: 现代C++的格式化工具库介绍与酷炫功能

libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库&#xff0c;提供了高效、安全的文本格式化功能&#xff0c;是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全&#xff1a…...