LeetCode之26.删除有序数组中的重复项和80.删除有序数组中的重复项II(C++)
文章目录
- 0 引言
- 1 删除有序数组中的重复项
- 1.1 解题方法
- 1.2 C++代码
- 2 删除有序数组中的重复项II
- 2.1 解题方法
- 2.2 C++代码
0 引言
本文主要记录如何解决LeetCode中数组和字符串类别中的26.删除有序数组中的重复项(简单)及80.删除有序数组中的重复项II (中等)两个问题。
1 删除有序数组中的重复项
给你一个 非严格递增排列 的数组
nums,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回nums中唯一元素的个数。
考虑nums的唯一元素的数量为k,你需要做以下事情确保你的题解可以被通过:
更改数组nums,使nums的前k个元素包含唯一元素,并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。
返回k。
👉 26.删除有序数组中的重复项
1.1 解题方法
双指针法[快慢指针]
首先务必要注意到数组是有序的,那么重复的数组一定是相邻的!
而题中要求删除重复的元素并只保留一个,换个思路想:其实把重复的元素往数组后边移动即可实现删除的目的,最后只返回单一元素的有序数组。
那如何知道两个数组元素是否是重复的呢?有个比较好的方法就是双指针,即快慢指针的方法,使用两个指针,一个在前记作f,一个在后记作e,然后来比较前后两个指针对应的数组元素。
大致步骤:
- 比较
f和e位置的元素是否相等 - 如果相等,
e后移1位; 如果不相等,将e位置的元素复制到f+1位置上,f后移一位,e后移 1 位 重复上述过程,直到e等于数组长度 - 返回
f+1,即为新数组长度
复杂度分析:
时间复杂度: O ( n ) O(n) O(n)。 空间复杂度: O ( 1 ) O(1) O(1)。
1.2 C++代码
class Solution {
public:int removeDuplicates(vector<int>& nums) {int f = 0, e = 1;while (e < nums.size()){// nums是升序的,重复的元素肯定相邻,把重复的后边的数赋值到前边的一位if(nums[f] != nums[e]){nums[f+1] = nums[e];f++;}e++;}return f + 1;}
};
2 删除有序数组中的重复项II
给你一个有序数组
nums,请你 原地 删除重复出现的元素,使得出现次数超过两次的元素只出现两次 ,返回删除后数组的新长度。
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O ( 1 ) O(1) O(1) 额外空间的条件下完成。
👉 80.删除有序数组中的重复项II
2.1 解题方法
双指针法[快慢指针]
虽然该题在第1题的基础上,增加了空间复杂度的要求( O ( 1 ) O(1) O(1) ),但正如1.1中的复杂度分析,双指针法其实已经满足该要求,所以还是可以继续用快慢指针法,但该题是要求超过两次的元素才删除。
大致步骤:
- 首先判断数组
nums的长度,如果长度小于等于2,直接返回数组长度即可 - 如果数组长度大于
2,新建两个指针,一个在前记作f,一个在后移2位记作e - 比较
f和e位置的元素是否相等 - 如果相等,
e后移1位; 如果不相等,将e位置的元素复制到f+2位置上,f后移一位,e后移 1 位 重复上述过程,直到e等于数组长度 - 返回
f+2,即为新数组长度
复杂度分析:
时间复杂度: O ( n ) O(n) O(n)。 空间复杂度: O ( 1 ) O(1) O(1)。
2.2 C++代码
class Solution {
public:int removeDuplicates(vector<int>& nums) {if (nums.size() <= 2){return nums.size();}int f = 0, e = 2;while(e < nums.size()){if(nums[f] != nums[e]){nums[f + 2] = nums[e];f++; }e++;}return f + 2;}
};
总结来说,快慢指针算法的基本思想是使用两个指针,一个指针移动速度较快(快指针),另一个指针移动速度较慢(慢指针)。通过调整指针的移动速度和起始位置,可以实现不同的效果。
Reference:
- 26.删除有序数组中的重复项
- 80.删除有序数组中的重复项II
⭐️👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍🌔
相关文章:
LeetCode之26.删除有序数组中的重复项和80.删除有序数组中的重复项II(C++)
文章目录 0 引言1 删除有序数组中的重复项1.1 解题方法1.2 C代码 2 删除有序数组中的重复项II2.1 解题方法2.2 C代码 0 引言 本文主要记录如何解决LeetCode中数组和字符串类别中的26.删除有序数组中的重复项(简单)及80.删除有序数组中的重复项II &#…...
linux驱动之input子系统简述
文章目录 一、什么是input子系统二、内核代码三、代码分析 一、什么是input子系统 Input驱动程序是linux输入设备的驱动程序,我们最常见的就按键,触摸,插拔耳机这些。其中事件设备驱动程序是目前通用的驱动程序,可支持键盘、鼠标…...
嵌入式裸机架构的探索与崩塌
为什么会想着探索下嵌入式裸机的架构呢?是因为最近写了一个项目,项目开发接近尾声时,发现了一些问题: 1、项目中,驱动层和应用层掺杂在一起,虽然大部分是应用层调用驱动层,但是也存在驱动层调用…...
MySQL高级语句(第二部分)
MySQL高级语句(第二部分)一、视图表 create view1、视图表概述2、视图表能否修改?(面试题)3、基本语法3.1 创建3.2 查看3.3 删除 4、通过视图表求无交集值 二、case语句三、空值(null) 和 无值(’ ) 的区别四、正则表达式五、存储过程1、简介…...
HTML计时事件(JavaScript)网页电子钟+网页计时器
setTimeout("函数","未来指定毫秒后调用函数"); clearTimeout(setTimeout("函数","未来指定毫秒后调用函数")); <!DOCTYPE html> <html><head><meta charset"utf-8"><title></title>…...
使用群晖实现Videostation电影的大容量存储及分享教程
文章目录 1.使用环境要求2.制作视频分享链接3.制作永久固定视频分享链接 李哥和他的女朋友是一对甜蜜的情侣,但不幸的是,由于工作原因,他们目前分隔两地,无法常常亲密相伴。 这个距离让李哥特别怀念和女朋友一起在电影院观看电影的…...
后端大厂面试-15道题
1. 说说计算机存储结构 计算机存储结构通常包括这几个层次: 主存储器(Main Memory):也称为内存(RAM,Random Access Memory),主要用于存储当前正在执行的程序和数据。它是计算机中最…...
C++: 冒泡排序(Bubble Sort)
假设你有一列由数字组成的玻璃珠,这些珠子的重量不同,你希望将它们按照重量从轻到重排列。你会这样做: 从左到右,比较相邻的两颗珠子的重量。如果左边的珠子比右边的珠子重,就交换它们的位置。然后,继续向…...
跨域的解决方案
文章目录 概念一、什么是跨域问题二、为什么会发生跨域问题三、跨域解决方案1、JSONP2、添加响应头3、Spring注解CrossOrigin4、配置文件(常用)5、nginx跨域 概念 一、什么是跨域问题 前端调用的后端接口不属于同一个域(域名或端口不同&…...
如何使用Java语言判断出geek是字符串参数类型,888是整数参数类型,[hello,world]是数组参数类型,2.5是双精度浮点数类型?
如何使用Java语言判断出geek是字符串参数类型,888是整数参数类型,[hello,world]是数组参数类型,2.5是双精度浮点数类型? Java是一种静态类型的编程语言,这意味着我们需要在编译时为变量指定具体的类型。但是ÿ…...
9.20华为机试-后端
1、丢失报文的位置 某通信系统持续向外发送报文,使用数组 nums 保存 n个最近发送的报文,用于在报文未达到对端的情况下重发。报文使用序号 sn 表示,序号 sn 按照报文发送顺序从小到大排序,相邻报文 sn 不完全连续且有可能相同。报…...
LC926. 将字符串翻转到单调递增(JAVA - 动态规划)
将字符串翻转到单调递增 题目描述动态规划 题目描述 难度 - 中等 LC926. 将字符串翻转到单调递增(JAVA - 动态规划) 如果一个二进制字符串,是以一些 0(可能没有 0)后面跟着一些 1(也可能没有 1)的形式组成的࿰…...
【高阶数据结构】哈希的应用 {位图;std::bitset;位图的应用;布隆过滤器;布隆过滤器的应用}
一、位图 1.1 位图概念 面试题 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。【腾讯】 遍历查找:内存中无法存放40亿个整数(约占内存15-16G);时间复杂…...
金融生产存储亚健康治理:升级亚健康 3.0 ,应对万盘规模的挑战
随着集群规模的不断扩大,硬盘数量指数级上升,信创 CPU 和操作系统、硬盘多年老化、物理搬迁等多种复杂因素叠加,为企业的存储亚健康管理增加了新的挑战。 在亚健康 2.0 的基础上,星辰天合在 XSKY SDS V6.2 实现了亚健康 3.0&#…...
C语言自定义类型讲解:结构体,枚举,联合(2)
🐵本篇文章将会对位段、枚举和联合的相关知识进行讲解 1. 位段📚 1.1 什么是位段 位段的声明和结构体类似,但是有两点不同: 1.位段的成员必须是int,unsigned int,signed int (C99之后也可以是其他成员&am…...
AI编程助手 Amazon CodeWhisperer 全面解析与实践
目录 引言Amazon CodeWhisperer简介智能编程助手智能代码建议代码自动补全 提升代码质量代码质量提升安全性检测 支持多平台多语言 用户体验和系统兼容性用户体验文档和学习资源个性化体验系统兼容性 功能全面性和代码质量功能全面性代码生成质量和代码安全性 CodeWhisperer的代…...
利用EXCEL进行XXE攻击
利用EXCEL进行XXE攻击 原因 原因 Microsoft Office从2007版本引入了新的开放的XML文件格式,新的XML文件格式基于压缩的ZIP文件格式规范,由许多部分组成。 我们可以将其解压缩到特定的文件夹中来查看其包含的文件夹和文件,可以发现其中多数是…...
芯片验证就是一次旅行
如果你国庆希望去一个你不曾去过的城市旅行,比如“中国苏州”。对游客来说,它是个蛮大的城市,有许多景点可以游玩,还有许多事情可以做。但实际上,即使最豪也最清闲的游客也很难看苏州的所有方方面面。同样的道理也适用…...
Java深入理解线程的三大特性
目录 1 CPU缓存导致可见性问题2 线程切换导致原子性问题3 性能优化导致有序性问题4 JMM(Java Memory Model)5 volatile6 synchronized 1 CPU缓存导致可见性问题 线程的三大特性: 可见性:Visibility有序性:Ordering原子性:Atomic…...
2025快手校招面试真题汇总及其解答(二)
6. hashmap数据结构 HashMap 是一种散列表,它是一种根据键值对来存储数据的数据结构。HashMap 的特点是插入、查找和删除操作的时间复杂度都是 O(1),因此它是一种非常高效的数据结构。 HashMap 的工作原理是将键值对存储在一个数组中,每个键值对都由一个哈希函数来映射到数…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
wpf在image控件上快速显示内存图像
wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像(比如分辨率3000*3000的图像)的办法,尤其是想把内存中的裸数据(只有图像的数据,不包…...
CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!
本文介绍了一种名为AnomalyAny的创新框架,该方法利用Stable Diffusion的强大生成能力,仅需单个正常样本和文本描述,即可生成逼真且多样化的异常样本,有效解决了视觉异常检测中异常样本稀缺的难题,为工业质检、医疗影像…...
ui框架-文件列表展示
ui框架-文件列表展示 介绍 UI框架的文件列表展示组件,可以展示文件夹,支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项,适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...
工厂方法模式和抽象工厂方法模式的battle
1.案例直接上手 在这个案例里面,我们会实现这个普通的工厂方法,并且对比这个普通工厂方法和我们直接创建对象的差别在哪里,为什么需要一个工厂: 下面的这个是我们的这个案例里面涉及到的接口和对应的实现类: 两个发…...
