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

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)

UniApp 集成腾讯云 IM 富媒体消息全攻略&#xff08;地理位置/文件&#xff09; 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型&#xff0c;核心实现方式&#xff1a; 标准消息类型&#xff1a;直接使用 SDK 内置类型&#xff08;文件、图片等&#xff09;自…...

Axure 下拉框联动

实现选省、选完省之后选对应省份下的市区...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...