当前位置: 首页 > 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…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...