面试经典150题——删除有序数组中的重复项

目录

题目链接:26. 删除有序数组中的重复项 - 力扣(LeetCode)

题目描述

判题标准:

示例

提示:

解法一:双指针

Java写法:

运行时间

C++写法:

运行时间

论屎山代码是如何出现的

时间复杂度和空间复杂度

总结


题目链接:26. 删除有序数组中的重复项 - 力扣(LeetCode)

注:下述题目描述和示例均来自力扣

题目描述

给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:

  • 更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案int k = removeDuplicates(nums); // 调用assert k == expectedNums.length;
for (int i = 0; i < k; i++) {assert nums[i] == expectedNums[i];
}

如果所有断言都通过,那么您的题解将被 通过

示例

示例 1:

输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2,并且原数组 nums 的前两个元素被修改为 1, 2 。
不需要考虑数组中超出新长度后面的元素。

示例 2:

输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示:

  • 1 <= nums.length <= 3 * 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 已按 非严格递增 排列


解法一:双指针

        在给定的整数数组(或在这个例子中是std::vector<int>)中移除重复项,使得每个元素最多只出现两次,并返回移除重复项后数组的新长度(即不包含被移除元素的部分)。不过,根据代码的实际逻辑,它实际上是在原地(in-place)修改数组,移除所有重复超过两次的元素,并返回剩余元素(即不重复或只重复一次)的数量。这里有一点小误解,因为通常“移除重复项”的表述可能意味着删除所有重复项,只保留唯一的元素,但这段代码实际上是保留最多两次出现的元素。

具体实现思路如下:

  1. 初始化指针:使用两个指针(或在这个例子中的索引变量)来遍历数组。一个指针(或索引)change用于跟踪当前应该放置新元素(即不重复或只重复一次的元素)的位置,另一个指针(或索引)findToChange用于遍历整个数组以查找下一个可能的新元素。

  2. 遍历数组:通过循环遍历数组(从第二个元素开始,因为第一个元素总是可以被视为“新元素”),比较findToChange指向的元素与findToChange - 1指向的元素是否相等。

  3. 比较与替换

    • 如果不相等,说明找到了一个新的元素(或该元素尚未达到两次出现),则将其复制到change指向的位置,并将changefindToChange都向前移动一位,以便继续查找下一个新元素。
    • 如果相等,说明当前元素是重复的,且前一个元素与它相同,因此不需要将其复制到新位置。只需将findToChange向前移动一位,以继续检查下一个元素。
  4. 返回结果:当遍历完整个数组后,change指针(或索引)将指向最后一个新元素之后的位置,即数组应该被截断的位置。因此,change的值(作为索引)就是移除重复项后数组的新长度。

  5. 注意:虽然这段代码没有显式地“删除”或“移除”任何元素,但它通过覆盖重复元素并返回新长度的方式,在逻辑上实现了移除重复项的效果。如果需要物理上从数组中删除元素,那么可能需要使用支持动态大小调整的容器(如std::vector),并在最后调用resize方法来截断数组到新的长度。不过,在这个特定的实现中,由于std::vector的大小并未改变,只是返回了一个表示有效元素数量的新长度,因此没有必要进行物理删除。

Java写法:

class Solution {public int removeDuplicates(int[] nums) {int len = nums.length;int change = 1;int findToChange = 1;while(findToChange < len){// 0,0,1,1,1,2,2,3,3,4//   l rif(nums[findToChange] != nums[findToChange - 1]){// 如果前后的值不相等的话就替换一下nums[change] = nums[findToChange];// 赋值完成之后就指针全部后移change++;findToChange++;}else {findToChange++;}}// 最后change指针所在的位置就是合理数组的长度return change;}
}

运行时间


C++写法:

class Solution {  
public:  int removeDuplicates(std::vector<int>& nums) {  int len = nums.size();  int change = 1;  int findToChange = 1;  while (findToChange < len) {  // 检查当前元素是否与前一个元素相等  if (nums[findToChange] != nums[findToChange - 1]) {  // 如果不相等,则将当前元素放到change指针指向的位置  nums[change] = nums[findToChange];  // 指针后移  change++;  }  // 无论是否相等,findToChange都需要后移以检查下一个元素  findToChange++;  }  // 最后change指针所在的位置(也就是下一个应该放置新元素的位置)即为无重复元素数组的长度  return change;  }  
};

运行时间


论屎山代码是如何出现的

class Solution {public int removeDuplicates(int[] nums) {// 获取原数组的长度int len = nums.length;// 定义出指针int change = 1;int findToChange = 1;int resLen = 1;while(findToChange < len && change < len){// 定位好初始的位置if(change == findToChange && nums[change] != nums[change - 1]){change++;findToChange++;resLen++;}else{// change指针就位了if(nums[findToChange] == nums[change]){findToChange++;}else {while(findToChange < len && nums[findToChange - 1] == nums[findToChange]){findToChange++;}if(findToChange < len){// findToChange指针就位了nums[change] = nums[findToChange];change++;findToChange++;resLen++;}}}}return resLen;}
}

        

        虽然也是过了,但是想的实在是复杂的要死,这种就是一开始没想明白就开始写,然后发现BUG,改BUG,代码屎山就是这样来的。

时间复杂度和空间复杂度


总结

        想好再写,先狠狠的思考一波再写兄弟们,不然容易整出屎山代码哦shift

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

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

相关文章

感知笔记2:ROS 视觉 - 沿线行走

如何在 ROS 中使用 OpenCV如何跟踪线路如何根据颜色查找不同元素跟踪多条路径并做出决定为线路跟踪创建基本的 PID 在本章中&#xff0c;您将学习如何使用 ROS 中最基本、最强大的感知工具&#xff1a;OpenCV。 OpenCV 是最广泛、最完整的图像识别库。有了​​它&#xff0c;…

Docker实操:安装MySQL5.7详解(保姆级教程)

介绍 Docker 中文网址: https://www.dockerdocs.cn Docker Hub官方网址&#xff1a;https://hub.docker.com Docker Hub中MySQL介绍&#xff1a;https://hub.docker.com/_/mysql ​ 切换到“Tags”页面&#xff0c;复制指定的MySQL版本拉取命令&#xff0c;例如 &#xff1a…

uv-ui组件的使用——自定义输入框的样式

一、官网的使用 二、自定义修改样式 我是在小程序中使用此组件 想要自定义修改样式的话&#xff0c;需要placeholderClass加上 placeholderStyle配合使用 tip1&#xff1a;单独使用placeholderClass&#xff0c;他只会第一次渲染时生效&#xff0c;输入文字再清除后就不生效…

十六,Spring Boot 整合 Druid 以及使用 Druid 监控功能

十六&#xff0c;Spring Boot 整合 Druid 以及使用 Druid 监控功能 文章目录 十六&#xff0c;Spring Boot 整合 Druid 以及使用 Druid 监控功能1. Druid 的基本介绍2. 准备工作&#xff1a;3. Druid 监控功能3.1 Druid 监控功能 —— Web 关联监控3.2 Druid 监控功能 —— SQL…

(蓝桥杯)STM32G431RBT6(TIM4-PWM)

一、基础配置 这个auto-reload preload是自动重装载值&#xff0c;因为我们想让他每改变一个占空比&#xff0c;至少出现一次周期 Counter Period(Autoreload Regisiter)这个设值为10000&#xff0c;那么就相当于它的周期是10000 脉冲宽度可以设置为占周期的一半&#xff0c;那…

Python酷库之旅-第三方库Pandas(123)

目录 一、用法精讲 546、pandas.DataFrame.ffill方法 546-1、语法 546-2、参数 546-3、功能 546-4、返回值 546-5、说明 546-6、用法 546-6-1、数据准备 546-6-2、代码示例 546-6-3、结果输出 547、pandas.DataFrame.fillna方法 547-1、语法 547-2、参数 547-3、…

opencv图像透视处理

引言 在图像处理与计算机视觉领域&#xff0c;透视变换&#xff08;Perspective Transformation&#xff09;是一种重要的图像校正技术&#xff0c;它允许我们根据图像中已知的四个点&#xff08;通常是矩形的四个角&#xff09;和目标位置的四个点&#xff0c;将图像从一个视…

Ubuntu 与Uboot网络共享资源

1、NFS 1.1 Ubuntu 下 NFS 服务开启 sudo apt-get install nfs-kernel-server rpcbind 等待安装完成&#xff0c;安装完成以后在用户根目录下创建一个名为“Linux”的文件夹&#xff0c;以后所有 的东西都放到这个“Linux”文件夹里面&#xff0c;在“Linux”文件夹里面新建…

[Simpfun游戏云1]搭建MC Java+基岩互通生存游戏服务器

众所周知&#xff0c;MC有多个客户端&#xff0c;像常见的比如Java Edition和基岩等&#xff0c;这就导致&#xff0c;比如我知道一个超级好玩的JE服务器&#xff0c;但我又想使用基岩版来玩&#xff0c;肯定是不行的&#xff0c;因为通讯协议不一样。 这就有一些人才发明了多…

搜索引擎onesearch3实现解释和升级到Elasticsearch v8系列(四)-搜索

搜索 搜索内容比较多&#xff0c;onesearch分成两部分&#xff0c;第一部分&#xff0c;Query构建&#xff0c;其中包括搜索词设置&#xff0c;设置返回字段&#xff0c;filter&#xff0c;高亮&#xff1b;第二部分分页和排序。第一部分是映射引擎负责&#xff0c;映射通用表…

常见中间件漏洞靶场(tomcat)

1.CVE-2017-12615 开启环境 查看端口 查看IP 在哥斯拉里生成一个木马 访问页面修改文件后缀和文件内容 放包拿去连接 2.后台弱⼝令部署war包 打开环境 将前边的1.jsp压缩成1.zip然后改名为1.war 访问页面进行上传 在拿去连接 3.CVE-2020-1938 打开环境 访问一下 来到kali …

错题集锦之C语言

直接寻址和立即寻址 算法的又穷性是指算法程序的运行时间是有限的 未经赋值的全局变量值不确定 集成测试是为了发现概要设计的错误 自然连接要求两个关系中进行比较的是相同的属性&#xff0c;并且进行等值连接&#xff0c;在结果中还要把重复的属性列去掉 赋值运算符 赋值…

【计算机网络篇】电路交换,报文交换,分组交换

本文主要介绍计算机网络中的电路交换&#xff0c;报文交换&#xff0c;分组交换&#xff0c;文中的内容是我认为的重点内容&#xff0c;并非所有。参考的教材是谢希仁老师编著的《计算机网络》第8版。跟学视频课为河南科技大学郑瑞娟老师所讲计网。 目录 &#x1f3af;一.划分…

无线安全(WiFi)

免责声明:本文仅做分享!!! 目录 WEP简介 WPA简介 安全类型 密钥交换 PMK PTK 4次握手 WPA攻击原理 网卡选购 攻击姿态 1-暴力破解 脚本工具 字典 2-Airgeddon 破解 3-KRACK漏洞 4-Rough AP 攻击 5-wifi钓鱼 6-wifite 其他 WEP简介 WEP是WiredEquivalentPri…

浅谈vue2.0与vue3.0的区别(整理十六点)

目录 1. 实现数据响应式的原理不同 2. 生命周期不同 3. vue 2.0 采用了 option 选项式 API&#xff0c;vue 3.0 采用了 composition 组合式 API 4. 新特性编译宏 5. 父子组件间双向数据绑定 v-model 不同 6. v-for 和 v-if 优先级不同 7. 使用的 diff 算法不同 8. 兄弟组…

2024年及未来:构筑防御通胀的堡垒,保护您的投资

随着全球经济的波动和不确定性&#xff0c;通货膨胀已成为投资者不得不面对的现实问题。通胀会侵蚀货币的购买力&#xff0c;从而影响投资的实际回报。因此&#xff0c;制定有效的策略来保护投资免受通胀影响&#xff0c;对于确保资产的长期增值至关重要。在2024年及未来&#…

nginx架构篇(三)

文章目录 一、Nginx实现服务器端集群搭建1.1 Nginx与Tomcat部署1. 环境准备(Tomcat)2. 环境准备(Nginx) 1.2. Nginx实现动静分离1.2.1. 需求分析1.2.2. 动静实现步骤 1.3. Nginx实现Tomcat集群搭建1.4. Nginx高可用解决方案1.4.1. Keepalived1.4.2. VRRP介绍1.4.3. 环境搭建环境…

口碑最好的头戴式耳机是哪些?高品质头戴式耳机对比测评揭晓

头戴式耳机以其出色的音质表现和舒适的佩戴体验&#xff0c;成为了音乐爱好者和日常通勤用户的热门选择。而在众多品牌和型号中&#xff0c;口碑最好的头戴式耳机是哪些&#xff1f;面对市场上丰富的选择&#xff0c;找到一款音质优良、佩戴舒适且性价比高的耳机并不容易。今天…

美畅物联丨技术前沿探索:H.265编码与畅联云平台JS播放器的融合应用

一、H.265 编码&#xff1a;视频压缩技术的重大变革 H.265&#xff0c;即被熟知为高效视频编码&#xff08;HEVC&#xff0c;High Efficiency Video Coding&#xff09;&#xff0c;由国际电信联盟电信标准化部门视频编码专家组&#xff08;ITU-T VCEG&#xff09;与国际标准化…

俄罗斯OZON新生儿产品好不好卖,OZON新生儿产品

Top1 遥控水球坦克 Танк на радиоуправлении стреляющий орбизами PANAWEALTH 商品id&#xff1a;1384249985 月销量&#xff1a;692 欢迎各位OZON卖家朋友点击这里选品&#xff1a; &#x1f449; D。DDqbt。COm/74rD 遥控射击水…