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 的工作原理是将键值对存储在一个数组中,每个键值对都由一个哈希函数来映射到数…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
