力扣面试经典算法150题:删除有序数组中的重复项 II

删除有序数组中的重复项 II

今天的题目是力扣面试经典150题中的数组的中等难度题: 删除有序数组中的重复项 II

题目链接:https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/description/?envType=study-plan-v2&envId=top-interview-150

题目描述

给定一个排序好的数组 nums,请原地删除重复出现的元素,使得每个元素最多出现两次,并返回删除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

  • 示例:
    • 输入:
      nums = [1,1,1,2,2,3]
    • 输出:
      [1,1,2,2,3], 新长度为 5
    • 输入:
      nums = [0,0,1,1,1,1,2,3,3]
    • 输出:
      [0,0,1,1,2,3,3], 新长度为 7

题目分析

题目要求我们删除一个已排序数组中的重复元素,使得每个元素最多出现两次。我们需要在原地修改数组,并且只能使用常数级别的额外空间。

重点注意的地方是已排序的数组,因为已排序的数组,有需要原数组操作比较,我们可以优先考虑一下双指针法进行求解。在移出重复元素的简单难度中也分析过。只不过我们需要考虑得到是之前移出到只有一个元素,现在保留两个,那么我们指针的间距和起始位置也要修改。

解题思路

直接考虑双指针法,需要注意的就是两个指针的作用及起始位置。

双指针法:

  1. 特殊情况长度不足的直接返回。
  2. 定义一个慢指针,用于去重后的数组指针,指针大小为2,因为作为有序数组,前两个元素可以直接放入到结果数组中。
  3. 定义一个快指针,对数组进行循环,并且从索引2开始进行,因为有序数组,前两个一定是符合要求的元素。
  4. 当前数组的元素(快指针)与结果数组(慢指针)下标前两个位置的元素进行比较。如果值不相同,说明这个元素需要放到结果数组中去,同时因为放入结果数组,慢指针的值需要加1。如果相等跳过无需处理。

最后输出慢指针的值,就是结果数组的长度。

实际算法代码

下面是通过以上分析使用双指针法的 Java 实现:

public class RemoveDuplicatesII {public static void main(String[] args) {RemoveDuplicatesII solution = new RemoveDuplicatesII();// 示例数据int[] nums = {1, 1, 1, 2, 2, 3};// 调用删除重复项的方法int newLength = solution.removeDuplicatesFastSlow(nums);// 输出结果System.out.println("New length : " + newLength);}/*** 删除有序数组中的重复项 II:双指针法(快慢指针)** @param nums 排序好的数组* @return 删除重复项后的数组新长度*/public int removeDuplicatesFastSlow(int[] nums) {if (nums.length <= 2) {return nums.length;}int slow = 2;for (int fast = 2; fast < nums.length; fast++) {if (nums[fast] != nums[slow - 2]) {nums[slow] = nums[fast];slow++;}}return slow;}
}

结果

执行函数,测试通过:

在这里插入图片描述

提交到力扣,测试也通过:

在这里插入图片描述

总结

在对有序数组的问题解决中,双指针法是非常实用的。目前为止已经用了好几次了。所以熟练掌握双指针法,对于数组方面的算法问题的解决会有很大帮助。

中等难度第一题,搞定!!!

感觉还行,加油!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/405713.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

时间序列分析2|ARIMA模型|SARIMA模型

ARMA模型的定阶 自相关和偏自相关系数法 通过观察样本的自相关系数(ACF)和偏自相关系数(PACF)&#xff0c;进行大体的判断 模型定阶的经验方法 截尾&#xff1a; 最初的d阶样本(偏)自相关系数明显在2倍标准差范围外95%的(偏)自相关系数都落在2倍标准差的范围以内非零自相…

【论文阅读】通用的语义-几何表征的机器人操作

文章目录 1. 【2023CoRL】A Universal Semantic-Geometric Representation for Robotic Manipulation针对痛点和贡献引言模型框架思考不足之处 2. Leveraging Locality to Boost Sample Efficiency in Robotic Manipulation摘要和结论引言模型框架实验思考不足之处 1. 【2023Co…

ES6-ES13学习笔记

目录 初识ES6 变量声明 解构赋值 对象解构 ​编辑 数组解构 ​编辑模版字符串 字符串扩展 includes() repeat() startsWith() endsWith() 数值扩展 二进制和八进制表示法 &#xff08;Number.&#xff09;isFinite()与isNaN() Number.isInteger() Math.trunc …

Leetcode JAVA刷刷站(69)x的平方根

一、题目概述 二、思路方向 在Java中&#xff0c;计算一个非负整数x的算术平方根&#xff0c;并返回其整数部分&#xff0c;你可以使用二分查找法。这是因为平方根函数是单调递增的&#xff0c;所以我们可以利用二分查找在合理的时间复杂度内找到结果。 三、代码实现 public…

Matplotlib入门与进阶:数据可视化的强大工具

Matplotlib入门与进阶&#xff1a;数据可视化的强大工具 在当今数据驱动的世界中&#xff0c;数据可视化成为了数据分析的重要一环。数据可视化不仅能够帮助开发者理解和分析数据&#xff0c;还能使数据展示更具说服力。本文将详细介绍Python中的2D绘图库——Matplotlib。通过…

Python自准直仪双筒望远镜光学ABCD矩阵行为算法

&#x1f3af;要点 &#x1f3af;平面&#xff1b;曲面&#xff1b;圆柱面&#xff1b;非球面光&#xff0c;双凸透镜&#xff1b;90 度棱镜&#xff1b;分束立方体&#xff0c;双透镜棱&#xff1b;镜分光镜光线&#xff1b;横置隔膜&#xff1b;全内反射&#xff1b;多个分束…

作业08.21

服务器&#xff1a; #include <myhead.h>#define SER_PORT 6666 #define SER_IP "127.0.0.1"int find_client(int *client_arr, int len, int client) {for(int i0; i<len; i){if(client_arr[i] client){return i;}}return -1; }void remove_client(int *…

python爬虫--pyquery解析库整理

前言 欢迎来到我的博客 个人主页:北岭敲键盘的荒漠猫-CSDN博客 本文整理python的爬虫解析库pyquery的语法 简洁快速的整理&#xff0c;建议有前端基础的人看 pyquery解析原理 pyquery的原理就是拿到网站的前端源码后&#xff0c;我们根据我们需求信息所在的标签进行筛选。 选…

漏洞挖掘 | 记一次edusrc--轻松拿下中危信息泄露

1.前言 也是一次漏洞挖掘的思路分享 上次我们讲过了关于小程序方面的一些小思路&#xff0c;即关于抓包更改id号造成的一个信息泄露&#xff0c;但是在小程序上的信息泄露很难涉及到公民三要素这是一个痛点&#xff0c;今天就来分享一下一次edu挖掘时挖到的一个涉及公民三要素…

【云备份】项目总结

文章目录 项目总结项目总结项目扩展:常见问题: 项目总结 项目总结 搭建云备份服务器与客户端&#xff0c;客户端程序运行在客户机上自动将指定目录下的文件备份到服务器&#xff0c;并且能够支持浏览器查看与下载&#xff0c;其中下载支持断点续传功能&#xff0c;并且服务器端…

kubernetes的pod基础

kubernetes的pod基础 pod概念 pod&#xff08;豆荚&#xff09;&#xff0c;是k8s的最小管理单元。是一个或多个容器的组合&#xff0c;这些容器共享存储&#xff0c;网络和命名空间&#xff0c;以及运行规范&#xff0c;pod内的容器统一的进行安排和调度。pod是一组具有共享命…

【TCP/IP】自定义应用层协议,常见端口号

互联网中&#xff0c;主流的是 TCP/IP 五层协议 5G/4G 上网&#xff0c;是有自己的协议栈&#xff0c;要比 TCP/IP 更复杂&#xff08;能够把 TCP/IP 的一部分内容给包含进去了&#xff09; 应用层 可以代表我们所编写的应用程序&#xff0c;只要应用程序里面用到了网络通信…

进程间的通信3——IPC对象通信->共享内存、网络通信

一、共享内存 1、原理 直接对实际物理内存进行操作&#xff0c;不用先拷贝到用户空间再到内核空间&#xff08;物理内存&#xff09;。 2、特点 &#xff08;1&#xff09;共享内存是一块内核预留的空间&#xff1b; &#xff08;2&#xff09;最高效的通信方式。 3、操作 产…

springboot+Quartz通过数据库控制定时任务执行与时间

前言 在我们的springboot项目中&#xff0c;有很多种实现定时任务的方式 有用最简单的 Scheduled 实现定时任务,即&#xff1a; import org.springframework.scheduling.annotation.Scheduled; import org.springframework.stereotype.Component;Component EnableScheduling p…

【RTT-Studio】详细使用教程十三:UART的DMA 接收及轮询发送

文章目录 一、简介二、RTT配置三、使用信号量接收四、使用消息队列接收五、测试验证 一、简介 串口是指数据一位一位地顺序传送&#xff0c;其特点是通讯线路简单&#xff0c;只要一对传输线就可以实现双向通信&#xff08;可以直接利用电话线作为传输线&#xff09;&#xff0…

我的创作纪念日【2048】

机缘 2048&#xff0c;是计算机二进制世界里很奇妙的数字&#xff0c;在CSDN上创作的第六年&#xff0c;记录从事本行业的知识学习与总结&#xff0c;好记性不如烂笔头&#xff0c;或许写的东西不如大佬的文章&#xff0c;那么有深度&#xff0c;但自己也是在坚持&#xff0c;…

自动微分autograd实践要点

目录 定义Value手动定义每个 operator 的 _backward() 函数构建反向传播计算链 本文主要参考 反向传播和神经网络训练 大神Andrej Karpathy 的“神经网络从Zero到Hero 系列”之一&#xff0c;提炼一些精要&#xff0c;将反向传播的细节和要点展现出来 定义Value 第一步首先要…

传知代码-自动化细胞核分割与特征分析(论文复现)

代码以及视频讲解 本文所涉及所有资源均在传知代码平台可获取 引言 细胞核分割和分类在医学研究和临床诊断中具有重要意义。精准的细胞核分割能够帮助医生更好地识别和分析细胞核的形态学特征&#xff0c;从而辅助疾病诊断、癌症检测以及药物研发。HoverNet是一种基于深度学…

【GitLab】使用 Docker engine安装 GitLab 2: gitlab-ce:17.3.0-ce.0 拉取

ce版本必须配置代理。 极狐版本可以直接pull 社区版GitLab不支持Alibaba Cloud Linux 3,本操作以Ubuntu/Debian系统为例进行说明,其他操作系统安装说明,请参见安装社区版GitLab。 docker 环境重启 sudo systemctl daemon-reload sudo systemctl restart docker脚本安装 安裝…

苹果手机微信聊天记录删除了怎么恢复?

在日常使用手机的过程中&#xff0c;我们经常会遇到误删微信聊天记录的情况&#xff0c;尤其是对于那些重要的对话记录&#xff0c;一旦丢失可能会带来不小的困扰。今天&#xff0c;我们就来探讨一下如何在苹果手机上恢复被删除的微信聊天记录。 一、利用第三方数据恢复工具 对…