Leetcode 删除有序数组中的重复项 Ⅱ

使用双指针来解决此问题,关键词“有序”数组,一个 index 指针用于构建新数组,一个 i 指针用于遍历整个数组
以下是代码的中文解释以及算法思想:
算法思想
这道题要求对一个有序数组进行去重,使得每个元素最多出现两次。我们需要在原数组上进行操作,不能使用额外的空间。为了实现这个要求,我们可以使用双指针法来完成:
-
初始化两个指针:
index指针表示下一个可以插入的有效位置(用于构建结果数组),它初始值为 2,因为前两个元素无论如何都可以直接保留。i指针遍历整个数组,从第三个元素开始检查(因为我们允许每个元素最多出现两次,所以不需要检查前两个元素)。
-
条件检查:
- 对于每个元素
nums[i],我们检查它是否等于nums[index - 2]。如果不等,则表示nums[i]至少可以插入到当前构建的结果数组中。 - 如果
nums[i] != nums[index - 2],则将nums[i]放到nums[index]位置上,并将index指针向后移动一位,准备下一个位置。
- 对于每个元素
-
返回结果:
- 最终
index的值就是新数组的长度,因为index指针的值代表了有效数组的长度。 - 原数组前
index个元素就是去重后的数组,且每个元素最多出现两次。
- 最终
代码示例
public class Solution {public int removeDuplicates(int[] nums) {if (nums.length <= 2) return nums.length;int index = 2; // 从第三个元素开始检查for (int i = 2; i < nums.length; i++) {// 如果当前元素 nums[i] 不等于 nums[index - 2],说明该元素可以加入if (nums[i] != nums[index - 2]) {nums[index] = nums[i];index++;}}return index;}
}
具体解释
- 数组长度小于等于 2:如果数组长度不超过 2,直接返回数组长度,因为每个元素都可以出现两次。
- 遍历数组:
- 从第三个元素开始(
i = 2),逐个检查每个元素nums[i]。 - 如果当前元素
nums[i]不等于nums[index - 2],表示当前元素没有超过出现两次的限制。 - 将当前元素
nums[i]放到nums[index]位置上,然后将index向后移动一位。
- 从第三个元素开始(
- 返回结果:
index的值就是数组去重后的长度,数组的前index个元素就是符合要求的结果。
复杂度分析
- 时间复杂度:O(n),因为我们只遍历了一遍数组。
- 空间复杂度:O(1),因为我们在原数组上进行操作,没有使用额外的空间。
示例
假设输入数组为 {1, 1, 1, 2, 2, 3}:
- 初始状态:
index = 2 - 遍历:
i = 2,nums[i] = 1,nums[index - 2] = 1,相等,跳过此元素。i = 3,nums[i] = 2,nums[index - 2] = 1,不相等,将nums[i]赋值给nums[index],index增加 1。i = 4,nums[i] = 2,nums[index - 2] = 1,不相等,将nums[i]赋值给nums[index],index增加 1。i = 5,nums[i] = 3,nums[index - 2] = 2,不相等,将nums[i]赋值给nums[index],index增加 1。
- 最终结果:返回的长度
index = 5,即{1, 1, 2, 2, 3}
java 代码如下:
class Solution {public int removeDuplicates(int[] nums) {// if (nums.length <= 2) return nums.length;int index = 2;for(int i = 2; i < nums.length; ++i) {if(nums[i] != nums[index - 2]) { //注意是index - 2, 而不是 i - 2nums[index++] = nums[i];}}return index;}
}
为什么这行代码的判断条件不是nums[i] != nums[i - 2]
if (nums[i] != nums[index - 2]) {
这是一个很好的问题。之所以判断条件写成 nums[i] != nums[index - 2] 而不是 nums[i] != nums[i - 2],是因为我们希望使用 index 指针来追踪构建新数组的有效长度,并确保每个元素最多出现两次。下面是具体原因:
原因解释
-
index指针的作用:index指针代表的是新数组的当前位置,也就是我们构建的、符合条件的数组的长度。index - 2始终指向新数组的倒数第二个元素。因此,nums[index - 2]可以用来判断当前的nums[i]是否已经出现了两次。
-
避免原数组的重复元素影响判断:
- 如果直接用
nums[i - 2],它表示的是原数组的倒数第二个元素。然而,我们的目标是构建一个新的符合条件的数组,这个数组并不直接等同于原数组。 - 例如,在原数组中,某个元素可能已经出现多次,但在新数组(由
index控制)中它可能只出现了一次。因此,判断条件需要使用nums[index - 2]而不是nums[i - 2]。
- 如果直接用
-
控制新数组的内容:
- 通过
nums[index - 2],我们可以确保只有符合条件的元素才被添加到新数组中,避免出现超过两次的重复。 - 如果使用
nums[i - 2],则我们判断的是原数组中的元素而不是新构建的数组,可能会导致多次重复的元素被错误地加入。
- 通过
举例说明
假设输入数组为 {1, 1, 1, 2, 2, 3}:
-
初始时
index = 2,我们从第三个元素(i = 2)开始遍历。- 当
i = 2时,nums[i] = 1,如果我们使用nums[i - 2]进行判断,那就是nums[0] = 1。此时,它会与nums[i]相等,判断条件为false,意味着它会被加入到新数组中,导致1出现三次,这是不符合题意的。 - 而使用
nums[index - 2](即nums[0] = 1)作为判断条件时,我们可以正确地跳过这个元素,避免多余的重复。
- 当
通过使用 index 指针,我们有效地控制了新数组的内容,并保证每个元素最多出现两次。
相关文章:
Leetcode 删除有序数组中的重复项 Ⅱ
使用双指针来解决此问题,关键词“有序”数组,一个 index 指针用于构建新数组,一个 i 指针用于遍历整个数组 以下是代码的中文解释以及算法思想: 算法思想 这道题要求对一个有序数组进行去重,使得每个元素最多出现两…...
大模型学习笔记------什么是大模型
大模型学习笔记------什么是大模型 1、大模型定义2、大模型发展历程3、大模型的核心特点4、大模型的应用领域5、大模型面临的挑战6、结束语 近两年大模型超级火,并且相关产品迎来爆发式增长。在工作中,也常常接触到大模型,并且已经开始进行相…...
【unique_str 源码学习】
文章目录 1.删除器定义2. operator->() 运算符重载3. add_lvalue_reference<element_type>::type 使用 基本原理这篇博主写的很详细 https://yngzmiao.blog.csdn.net/article/details/105725663 1.删除器定义 deleter_…...
flask第一个应用
文章目录 安装一、编程第一步二、引入配置三、代码解析 安装 python环境安装的过程就不重复赘述了,flask安装使用命令pip install Flask即可,使用命令pip show Flask查看flask版本信息 提示:以下是本篇文章正文内容,下面案例可供…...
华为OD机试真题(Python/JS/C/C++)- 考点 - 细节
华为OD机试 2024E卷题库疯狂收录中,刷题 点这里。 本专栏收录于《华为OD机试真题(Python/JS/C/C)》。...
【C++刷题】力扣-#628-三个数的最大乘积
题目描述 给你一个整型数组 nums ,在数组中找出由三个数组成的最大乘积,并输出这个乘积。 示例 示例 1 输入:nums [1,2,3] 输出:6示例 2 输入:nums [1,2,3,4] 输出:24示例 3 输入:nums […...
Java项目实战II基于Java+Spring Boot+MySQL的工程教育认证的计算机课程管理平台(源码+数据库+文档)
目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发,CSDN平台Java领域新星创作者,专注于大学生项目实战开发、讲解和毕业答疑辅导。获取源码联系方式请查看文末 一、前言 随着工程教…...
基于微信小程序实现信阳毛尖茶叶商城系统设计与实现
作者简介:Java领域优质创作者、CSDN博客专家 、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、多年校企合作经验,被多个学校常年聘为校外企业导师,指导学生毕业设计并参与学生毕业答辩指导,…...
设计一个灵活的RPC架构
RPC架构 RPC本质上就是一个远程调用,需要通过网络来传输数据。传输协议可以有多种选择,但考虑到可靠性,一般默认采用TCP协议。为了屏蔽网络传输的复杂性,需要封装一个单独的数据传输模块用来收发二进制数据,这个单独模…...
大数据计算里的Broadcast Hash Join/Shuffle Hash Join/Sort Merge Join
文章目录 Broadcast Hash Join场景 Shuffle Hash Join场景 Sort Merge Join场景 Broadcast Hash Join 场景 大表和小小表,直接把B表加载到内存,然后读块1内容和内存中数据匹配 Shuffle Hash Join 场景 大表和小表JOIN ,小表分块后能加载…...
Java - 手写识别; 如何用spring ai和大模型做手写识别教程
识别后的文字 利用大模型提升Java手写识别:更简单、更高效 在Java场景中,我们经常需要处理手写识别的问题。过去,这类需求主要依赖于OCR技术,但其效果并不总是稳定。随着大模型的发展,使用大模型进行java手写识别成为…...
【Linux】用户权限管理:创建受限用户并配置特定目录访问权限
本文详细介绍了如何在 Linux 系统中创建一个名为 agent 的新用户,并限制其在特定目录下的权限。通过使用 useradd 命令创建用户,并使用 usermod 命令将新用户添加到现有用户组中,确保其具有适当的权限。接着,通过 chown 和 chmod …...
pgsql表分区和表分片设计
在设计 PostgreSQL 表分区和表分片时,主要目标是提高查询性能、可扩展性和数据管理的效率。以下是一些关键的设计步骤和策略: 1. 分区策略 水平分片:选择按日期进行水平分片,每天一个分片。这种策略适用于具有时间序列数据的场景…...
灵动AI ——视频创作新引擎 开启视觉奇幻之旅
灵动AI视频官网地址:https://aigc.genceai.com/ 灵动AI 科技与艺术的完美融合之作。它代表着当下最前沿的影像技术,为我们带来前所未有的视觉盛宴。...
AI设计、作图、画画工具哪个好用?看完这篇你就知道怎么选了
Stable Diffusion Stable Diffusion 是由 Stability AI 推出的开源 AI 文本到图像生成模型,以其开放性和灵活性在 AI 视觉工具领域广受欢迎。与 DALL-E 或 Midjourney 等只能依赖云计算的工具不同,Stable Diffusion 支持本地运行,也广泛兼容多…...
【python ASR】win11-从0到1使用funasr实现本地离线音频转文本
文章目录 前言一、前提条件安装环境Python 安装安装依赖,使用工业预训练模型最后安装 - torch1. 安装前查看显卡支持的最高CUDA的版本,以便下载torch 对应的版本的安装包。torch 中的CUDA版本要低于显卡最高的CUDA版本。2. 前往网站下载[Pytorch](https://pytorch.o…...
myqld二进制安装和破解数据库密码(linux)
安装和基本配置 1.首先把下载下来的mysql安装包放到本地这里下载的是5.7版本为演示 1)解压 tar xf mysql-5.7.20-linux-glibc2.12-x86_64.tar.gz -C /usr/local -把安装包解压到/usr/local cd /usr/local …...
防重方案-订单防重方案笔记
订单防重设计 订单重复提交概念解决方案前端防重机制后端防重机制利用Token机制基于数据库的唯一索引 Token机制方案介绍 其他 订单重复提交概念 重复提交指,连点按钮进行重复提交操作,不包括刷新后的重新下单,重新下单已非同一订单的概念。…...
HTML、JavaScript和CSS实现注册页面设计
目录 一、实现要求 二、实现页面图 1、注册页面 2.用户ID、用户名、口令验证成功后显示页面 三、用户ID、用户名、口令、确定口令验证逻辑js代码 1、验证用户ID 2、验证用户名 3、验证口令密码 四、总结 五、代码仓库 一、实现要求 综合使用HTML、JavaScript和CSS进…...
Counter对象的使用样例
1. Counter类的定义和功能说明 Counter是一个用于跟踪值出现次数的有序集合。它可以接收一个可迭代对象作为参数,并生成一个字典,其中包含每个元素作为键,其计数作为值。 2. 统计列表或字符串中元素的出现次数 示例代码: from…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
