代码随想录刷题-数组-移除元素
文章目录
- 写在前面
- 习题
- 我的想法
- 暴力解法
- 双指针
写在前面
本节对应代码随想录中:代码随想录
习题
题目链接: 27. 移除元素- 力扣(LeetCode)
给你一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
你不需要考虑数组中超出新长度后面的元素。
我的想法
非较优答案,仅为个人思路记录
我的想法是 for 循环从头遍历 nums,并用 res 记录最终结果初始为0。如果当前遍历到的值等于 val,则让 res 位置和遍历到的 val 所在位置替换下,这样一轮 for 循环后前 res 位置都是 val。
新的长度用总长度减去 res 即可。而由于题目要求 nums 前 res 个要返回非 val 的数值,因此还要一轮 for 循环将前 res 个元素和后 res 个元素替换。
class Solution {public:int removeElement(vector<int>& nums, int val) {int n = nums.size(), res = 0, temp;for (int i = 0; i < n; i++) {if (nums[i] == val) {// 如果和val相等则和让当前值和前面的值替换temp = nums[i];nums[i] = nums[res];nums[res] = temp;res++;}}// 把和val相等的几个值放到后面for (int i = 0; i < res; i++) {temp = nums[i];nums[i] = nums[n - i - 1];nums[n - i - 1] = temp;}return n - res;}
};
后来看了题解后,想了下发现前 res 个可以直接删除而不用和后面 res 个替换
nums.erase(nums.begin(), nums.begin() + res);
暴力解法
两层 for 循环,第一层循环从头遍历数组,如果遇到和 val 相等的值,则用第二层 for 循环将当前位置之后的元素都像前移动一位。
例如 0 1 2 3 2 5,val=2
- 第一层 for 循环从左到右遍历,遇到 nums[2]=2时,将后面的 3 2 5向前移一位变成0 1 3 2 5
- 接着继续遍历(3 2 5),遇到第二个2时,将后面的5向前移一位变成0 1 3 5
题目中说了不用考虑超过新长度范围外的元素
代码如下:
需要注意的是向前移动一位后,i 要减1,如上面的例子,nums[2]=2,移动后变成0 1 3 2 5,此时若不减1下一次 i=3,将会跳过3与 val 的比较而是比较第二个2与 val。同时 size 减一方便记录新数组的长度。
// 时间复杂度:O(n^2)
// 空间复杂度:O(1)
class Solution {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();for (int i = 0; i < size; i++) {if (nums[i] == val) { // 发现需要移除的元素,就将数组集体向前移动一位for (int j = i + 1; j < size; j++) {nums[j - 1] = nums[j];}i--; // 因为下标i以后的数值都向前移动了一位,所以i也向前移动一位size--; // 此时数组的大小-1}}return size;}
};
与我自己想的解法相比,这个解法在找到 val 时将后面的元素向前移动一位,从而保证前面的元素都是题目要求的。
而我的解法是将找到的 val 放到前面,之后再把他们放到后面(直接放到后面会覆盖后面的元素)。
双指针
双指针:通过一个快指针和慢指针在一个for循环下完成两个for循环的工作
快指针从头遍历元素指向当前将要处理的元素,慢指针指向下一个将要赋值的位置。
- 如果快指针指向的元素不等于 val,它一定是输出数组的一个元素,我们就将快指针指向的元素复制到慢指针位置,然后将两个指针同时右移;
- 如果快指针指向的元素等于 val,它不能在输出数组里,此时慢指针不动,快指针右移一位。
这样左边的元素都不等于 val
与前面的两个解法相比,用慢指针替代了前面的第二个 for 循环。关键语句是 nums[slowIndex++] = nums[fastIndex];
将后面的值直接复制到前面合适的位置。
// 时间复杂度:O(n)
// 空间复杂度:O(1)
class Solution {
public:int removeElement(vector<int>& nums, int val) {int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {if (nums[fastIndex] != val) {nums[slowIndex++] = nums[fastIndex];}}return slowIndex;}
};
这里的快指针相当于常写的 for (int i = 0; i < size; i++)
中的 i 一样,遇到和 val 相等的值时,再用一个慢指针将和 val 相等的值移到前面。如果将 fastIndex 改成常写的 i 就会发现其实就是用 nums[slowIndex++] = nums[fastIndex];
解决了上面两种解法好几行才能解决的问题。
class Solution {
public:int removeElement(vector<int>& nums, int val) {int slowIndex = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] != val) {nums[slowIndex++] = nums[i];}}return slowIndex;}
};
总结:
- 我的想法遇到和 val 相等的元素先替换到前面再替换到后面
- 暴力解法遇到 val 相等的元素时,将后面的元素都向前移一位
- 双指针遇到 val 相等的元素时,用慢指针将后面的非 val 元素替换到前面的合适位置
相关文章:
代码随想录刷题-数组-移除元素
文章目录写在前面习题我的想法暴力解法双指针写在前面 本节对应代码随想录中:代码随想录 习题 题目链接: 27. 移除元素- 力扣(LeetCode) 给你一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素&a…...
聚观早报 |拼多多跨境电商业务正式登陆澳洲;中国加快6G网络研发
今日要闻:拼多多跨境电商业务正式登陆澳洲;全球自动驾驶公司排名特斯拉垫底;中国将加快 6G 网络研发;B站再次“崩”上热搜!已闪电修复;微软将必应AI聊天每次对话上限增加至8条拼多多跨境电商业务正式登陆澳…...
MDK Keil5 创建Stm32工程-理论篇(这里以Stm32F103Zet6为例)
一、文件夹创建与文件说明整个工程可以粗略的划分为几个文件夹:BSP底层驱动比如GPIO\Timer等驱动文件CMSIS内核相关的文件Firmware生成的固件下载文件Mycode用户编写的相关文件,主要编写的文件都在这个文件夹里Project工程文件startup芯片启动文件STM32F…...
应届大学生学什么技术好?哪些技术适合年轻人?
到了毕业季,应届大学生面临的就是就业问题,很多专业的大学生难以找到对口的工作,或是不得已随便就业,或者是学个技术高薪就业,那么,问题来了,应届大学生学什么技术好?哪些技术适合年…...
车企数据分类分级的实践指南出炉!“数据安全推进计划”发布,奇点云参编
日前,“数据安全推进计划”(DSI)正式发布《智能网联汽车数据分类分级实践指南》(下文简称“指南”),旨在以合规为主要导向,明确智能网联汽车数据分类分级的方法论,为数据全生命周期的…...
Nginx学习 (2) —— 虚拟主机配置
文章目录虚拟主机原理域名解析与泛域名解析(实践)配置文件中ServerName的匹配规则技术架构多用户二级域名短网址虚拟主机原理 为什么需要虚拟主机: 当一台主机充当服务器给用户提供资源的时候,并不是一直都有很大的用户量&#…...
Java 动态代理简述和实例
Java动态代理是一种在运行时动态创建代理对象的技术。它可以让我们在不修改原始代码的情况下,对原始对象进行增强或者添加额外的行为。这种代理方式可以用于很多场景,例如AOP编程、RPC框架等。动态代理是基于Java反射机制实现的,它允许程序在…...
Unity编译器扩展(Advanced Editor Scripting)
Untiy编译器扩展允许我们对编译器的增加自己编写的的功能菜单栏MenuItemContextMenu和ContextMenuItemContextMenuContextMenuItemMenuItem 该属性允许您将菜单项添加到主菜单和检查器窗口上下文菜单。 该属性将任何静态函数转换为菜单命令。只有静态函数可以使用该属性。 Men…...
AFR机制及流程介绍
AFR(Auto Fast Return)不符合3GPP协议标准,因此终端默认是disable状态。如果运营商有要求可以配置开启。 AFR有两种场景 2G或者3G AFR到4G4G AFR到5G3G AFR TO 4G AFR到LTE功能的作用就是终端从LTE Handover或者重定向到3G进行业务,等业务做完后能够快速回到LTE网络。...
9.Hbase 部署
9.Hbase部署 注意事项: 1:必须事先安装 Hadoop分布式集群,zookeeper分布式集群 2:查看版本号: hbase version1、解压文件并改名 tar -zxvf /opt/software/hbase-2.2.3-bin.tar.gz -C /usr/app/ mv hbase-2.2.3/ hba…...
【maven 学习记录】
maven 学习记录一、maven基础1. maven是什么2. maven的作用3. maven的下载安装4. maven仓库5. maven坐标6. 第一个maven项目 手工实现7. maven插件8. 依赖管理9. 生命周期二、maven进阶一、maven基础 1. maven是什么 maven的本质是一个项目管理工具,将项目开发和管…...
NB-IOT宣传这么多年,这次总算用好了吧
一、方案概述随着实体经济快速发展,石化、港口、货场、工地等区域规模日益扩大,厂区面积广阔、环境复杂、作业人员和车辆众多,如无法实时掌握工作人员状态及外来人员位置、外来车辆情况等问题,将存在非常大的安全隐患。今天小编介…...
sort函数对结构体|pair对组|vector容器|map排序|二维数组的第x列 的排序
目录 sort对 vector容器 sort对 vector<pair<int,int>>对组 sort对 结构体 结构体外部规定排序 结构体内部运算符重载 map容器的排序 map的键排序 map的值排序 sort对二维数组的排序 sort对 vector容器 sort()函数可以用于对vector容器进行排序。具体来…...
Java定时器Timer的使用
一、Timer常用方法 Timer应用场景: 1、每隔一段时间执行指定的代码逻辑(即按周期执行任务) 2、指定时间执行指定的代码逻辑 为方便测试并查看运行效果,首先先建一个类并继承TimerTask,代码如下: package timerTest…...
MySQL安装和配置
下载官网下载mysql解压版本:配置环境变量下载完成后直接解压到需要放的文件夹,根据文件夹来配置环境变量;新建系统变量,变量名自取,值是MySQL的目录编辑path环境变量,加上MySQL的bin目录 %MYSQL_HOME%\bin配…...
openpnnp - 载入板子后,要确定板子的放置角度
文章目录openpnnp - 载入板子后,要确定板子的放置角度概述用openpnp提供的功能来确定被夹住的板子的左下角原点位置和板子的角度备注ENDopenpnnp - 载入板子后,要确定板子的放置角度 概述 设备是有夹具的, 用百分表打过, 夹具本身在Z方向的平行度是没问题的. 但是, PCB板子的…...
HCIP知识点(前三天)
复习HCIA: 一、TCP/IP模型,OSI模型 OSI 开放式系统互联参考模型 应用层 抽象语言—>编码 表示层 编码—>二进制 会话层 应用程序内部的区分地址(无标准格式) 传输层 TCP/UDP – 分段(受MTU限制)、端…...
模板学堂丨妙用Tab组件制作多屏仪表板并实现自动轮播
DataEase开源数据可视化分析平台于2022年6月正式发布模板市场(https://dataease.io/templates/)。模板市场旨在为DataEase用户提供专业、美观、拿来即用的仪表板模板,方便用户根据自身的业务需求和使用场景选择对应的仪表板模板,并…...
C++:初识函数模板和类模板
目录 一. 泛型编程 二. 函数模板 2.1 什么是函数模板 2.2 函数模板的实例化 2.2.1 函数模板的隐式实例化 2.2.1 函数模板的显示实例化 2.3 函数模板实例化的原理 2.4 模板函数调用实例化原则 三. 类模板 3.1 什么是类模板 3.2 类模板的实例化 一. 泛型编程 泛型编程…...
3.8妇女节如何做好TikTok网红营销?
3月8日是国际妇女节,这一节日已经成为全球关注女性权益和平等的标志性日子,TikTok上话题#internationalwomensday累计播放超10亿次,话题#WomensDay2023累计播放量也将近300万次。 这个特别的日子为品牌提供了一个很好的营销机会。据Nox聚星了…...
使用Advanced Installer打包程序及运行环境
Advanced Installer 工具版本:20.1.1 设置产品信息 选中右侧【Product Details】输入产品信息 设置文件和文件夹 添加使用VS发布之后的程序文件夹 设置文件夹刷新 选中文件夹,右键选择属性,选中Synchronize标签。启用“Synchronize conten…...
华为OD机试真题Python实现【计算堆栈中的剩余数字】真题+解题思路+代码(20222023)
计算堆栈中的剩余数字 题目 向一个空栈中依次存入正整数 假设入栈元素N(1<=N<=2^31-1) 按顺序依次为Nx … N4、N3、N2、N1, 当元素入栈时,如果N1=N2+...Ny(y的范围[2,x],1 <= x <= 1000) 则 N1 到 Ny 全部元素出栈,重新入栈新元素M(M=2*N1) 如依次向栈存储6、1、…...
企业文件数据泄露防护(DLP)
什么是数据丢失防护 数据丢失防护 (DLP) 是保护数据不落入坏人之手的做法。如今,数据传输的主要问题是使大量数据容易受到未经授权的传输。通过设置足够的安全边界,您可以控制数据在网络中的移动。由于您的数据非常有价值&#x…...
不考虑分配与合并情况下,GO实现GCMarkSweep(标记清楚算法)
观前提醒 熟悉涉及到GC的最基本概念到底什么意思(《垃圾回收的算法与实现》)我用go实现(因为其他的都忘了,(╬◣д◢)ムキー!!) 源码地址(你的点赞,是我开源的…...
利用HGT聚类单细胞多组学数据并推理生物网络
单细胞多组学数据允许同时对多种组学数据进行定量分析,以捕捉复杂的分子机制和细胞异质性。然而现有的工具不能有效地推断不同细胞类型的活性生物网络以及这些网络对外部刺激的反应。 来自:Single-cell biological network inference using a heterogen…...
杂记——18.VSCode的下载及使用
这篇文章,我们来讲一下VSCode,讲一下如何下载及使用VSCode 目录 1.VSCode的下载 1.1VSCode的简介 1.2VSCode的下载与安装 1.2.1下载 1.2.2安装 2.VSCode的使用 2.1界面 2.2基础设置 2.3禁用自动更新 2.3自动保存设置 2.4Vscode更换主题 2.5…...
【独家】华为OD机试 - 最少停车数(C 语言解题)
最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧文章目录 最近更新的博客使用说明本期…...
顶级动漫IP加持之下,3A策略游戏Mechaverse如何改变GameFi
2021年是元宇宙发展的元年,元宇宙与GameFi创造了一波又一波市场热点。在经历第一波热潮之后,元宇宙的到来让不少人看到了加密市场的潜力,同时大家也意识到这将是未来的重要方向。如何将元宇宙推向更广阔的市场,让更多人能够轻松进…...
一款丧心病狂的API测试工具:Apifox!
你好,我是测试开发工程师——凡哥。欢迎和我交流测试领域相关问题(测试入门、技术、python交流都可以) 我们平时在做接口测试的时候,对于一些常用的接口测试工具的使用应该都非常熟悉了: 接口文档:Swagge…...
【前端学习】D2-2:CSS基础
文章目录前言系列文章目录1 Emmet语法1.1 快速生成HTML语法结构1.2 快速生成CSS样式语法1.3 快速格式化代码2 CSS复合选择器2.1 什么是复合选择器2.2 后代选择器(*)2.3 子选择器2.4 并集选择器(*)2.5 伪类选择器2.6 链接伪类选择器…...
公司模块网站制作/百度一下你就知道下
项目采用的是MVC模式对模块进行管理-沿用了家宝贝项目框架 一.首页模块(大概实现思路) 1 首页模块可分为三块.第一块在tableHeaderView上封装的图片轮播器.第二,三块是直接添加到tableView的cell上了. 2 八个按钮的位置是九宫格排布 分装的view高度是根据按钮个数来动态计算的.…...
网络工程有哪些/关键词优化教程
对话框不是模式就是无模式的。模式对话框,在可以继续操作应用程序的其他部分之前,必须被关闭(隐藏或卸载)。例如,如果一个对话框,在可以切换到其它窗 体或对话框之前要求先单击“确定”或“取消”ÿ…...
男女生做内个的网站/附近的成人电脑培训班
前言 我们前面学习到String类的相关知识,知道了它是一个字符串类,并且了解到其中的一些方法,但是当时并没有太过注意到String类的特点,今天就StringBuilder类的学习来比较一下两者的区别和作用.String类String类实例化的对象,其长度是固定不变的,其内容也是不可改变的. 那么,为…...
凡客网站登陆/指数基金怎么选
最近chrome浏览器更新后,发现以前设置的启动浏览器“重上次停下的地方继续”功能消失了。 当我点击设置网页时,会出现如上提示。 后来有同事给了如下一个连接,里面说到这个是公司的超级管理员搞的,他定义了,某个页面为…...
网站建设相对路径/关于进一步优化
中国智能语音助手企业案例研究报告(2018年)-笔记 1 摘要 目前行业里的智能语音助手主要应用于消费级产品和专业级行业应用两大领域。 智能语音助手的卖点是:想通过语音操控从而解放双手,并且智能语音助手对语音语义识别的准确性成为了用户选择及使用时…...
网络信息服务平台/seo运营专员
一转眼从学校毕业已经超过10年了,从一名普通的程序员成长为500强企业的架构师,如今也开始做IT管理工作,可以算是一个过来人。这一路走来,自己有一些感悟,也看到其他人的一些经验教训,对于如何掌控自己的职业…...