移除元素(双指针)
给你一个数组 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循环,一个for循环遍历数组元素 ,第二个for循环更新数组。
删除过程如下:
// 时间复杂度: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;}
};
- 时间复杂度:O(n^2)
- 空间复杂度:O(1)
双指针法
双指针法(快慢指针法): 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
定义快慢指针
- 快指针:寻找新数组的元素 ,新数组就是不含有目标元素的数组
- 慢指针:指向更新 新数组下标的位置
很多同学这道题目做的很懵,就是不理解 快慢指针究竟都是什么含义,所以一定要明确含义,后面的思路就更容易理解了。
双指针法(快慢指针法)在数组和链表的操作中是非常常见的,很多考察数组、链表、字符串等操作的面试题,都使用双指针法。
代码:
// 时间复杂度: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 (val != nums[fastIndex]) {nums[slowIndex++] = nums[fastIndex];}}return slowIndex;}
};
注意这些实现方法并没有改变元素的相对位置!
- 时间复杂度:O(n)
- 空间复杂度:O(1)
/**
* 相向双指针方法,基于元素顺序可以改变的题目描述改变了元素相对位置,确保了移动最少元素
* 时间复杂度:O(n)
* 空间复杂度:O(1)
*/
class Solution {
public:int removeElement(vector<int>& nums, int val) {int leftIndex = 0;int rightIndex = nums.size() - 1;while (leftIndex <= rightIndex) {// 找左边等于val的元素while (leftIndex <= rightIndex && nums[leftIndex] != val){++leftIndex;}// 找右边不等于val的元素while (leftIndex <= rightIndex && nums[rightIndex] == val) {-- rightIndex;}// 将右边不等于val的元素覆盖左边等于val的元素if (leftIndex < rightIndex) {nums[leftIndex++] = nums[rightIndex--];}}return leftIndex; // leftIndex一定指向了最终数组末尾的下一个元素}
};相关文章:
移除元素(双指针)
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的…...
76.qt qml-QianWindow开源炫酷界面框架(支持白色暗黑渐变自定义控件均以适配)
界面介绍界面支持: 透明 白色 黑色 渐变 单色 静态图 动态图侧边栏支持:抽屉、带折叠、多模式场景控件已集成: 暗黑风格 高亮风格、并附带个人自定义控件及开源demo白色场景如下所示:单色暗黑风格如下所示:用户自定义皮肤如下所示:皮肤预览如下所示:b站入口:https://www.bilibi…...
Python生日蛋糕
目录 前言 底盘 蛋糕 蜡烛 祝福 前言 Hello,小伙伴们晚上好吖!前两天博主满20岁啦(要开始奔三辽呜呜呜),这几天收到了不少小伙伴们的祝福,浪漫的小博主想送给大家一份不一样的生日蛋糕,…...
QT 如何提高 Qt Creator 的编译速度
如何提高编译速度,貌似是一个老生常谈的话题。对于Qter而言,如何提高QT Creator 的编辑速度是一直都是大家所期盼的。本文也是查阅了各路大神的方法后整理出来的,希望对各位有所帮助。 1、在*.pro文件添加预编译机制 QT官方给出的示例&…...
STM32之震动传感器、继电器介绍及实战
目录 一、震动传感器介绍及实战 二、编程代码实现 1、gpio.c---------初始化GPIO口引脚函数 2、调用中断服务函数 3、中断服务函数 4、中断服务回调函数 5、把上述的中断服务回调函数,放入main主函数里 6、结果演示 三、继电器介绍及实战 一、震动传感器介…...
RK3588平台开发系列讲解(显示篇)RK3588 平台 的DP介绍
平台内核版本安卓版本RK3588Linux 5.10Android 12文章目录 一、功能特性二、 DP 输⼊三、DP 输出四、 代码路径沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇将介绍 RK3588 平台 DP 的使⽤与调试⽅法。 一、功能特性 RK3588 的 DP ⽀持 1.4a 版本的 DP 协议,最…...
【Java】i++和++i的实现原理
文章目录 i++案例反编译分析扩展 x = x++我们接下来从字节码层面分析: 不了解字节码的可以参考这篇:【精通JVM】字节码指令全解 i++案例 package org.example;public class Main {public static void main...
第十四届蓝桥杯三月真题刷题训练——第 18 天
目录 第 1 题:排列字母 问题描述 运行限制 代码: 第 2 题:GCD_数论 问题描述 输入格式 输出格式 样例输入 样例输出 评测用例规模与约定 运行限制 第 3 题:选数异或 第 4 题:背包与魔法 第 1 题&#x…...
软件测试拿了几个20K offer,分享一波面经
1、你的测试职业发展是什么? 测试经验越多,测试能力越高。所以我的职业发展是需要时间积累的,一步步向着高级测试工程师奔去。而且我也有初步的职业规划,前3年积累测试经验,按如何做好测试工程师的要点去要求自己,不断…...
spring2
1.Spring配置数据源1.1 数据源(连接池)的作用 数据源(连接池)是提高程序性能如出现的事先实例化数据源,初始化部分连接资源使用连接资源时从数据源中获取使用完毕后将连接资源归还给数据源常见的数据源(连接池):DBCP、C3P0、BoneC…...
【Linux】网络编程套接字(中)
🎇Linux: 博客主页:一起去看日落吗分享博主的在Linux中学习到的知识和遇到的问题博主的能力有限,出现错误希望大家不吝赐教分享给大家一句我很喜欢的话: 看似不起波澜的日复一日,一定会在某一天让你看见坚持…...
手撕数据结构—队列
队列队列的话只允许在一端插入,在另外一端删除。插入数据的那一段叫做队尾,出数据的那一段叫做队头(从尾巴插入)。因此的话队列是先进先出的。入的顺序与出的顺序的话是一样的。这个与栈是不一样的,因为栈的话就是说如…...
gdb调试工具和makemakefile工具
gdb调试工具和make/makefile工具 文章目录gdb调试工具和make/makefile工具一、gdb调试工具1.debug/release2.使用二、make/makefile1.什么是make/makefile2.编写一、gdb调试工具 1.debug/release 程序有两种默认的发布方式debug和release。release是无法进行调试的。Linux中g…...
【进阶数据结构】平衡搜索二叉树 —— AVL树
🌈感谢阅读East-sunrise学习分享——[进阶数据结构]AVL树 博主水平有限,如有差错,欢迎斧正🙏感谢有你 码字不易,若有收获,期待你的点赞关注💙我们一起进步🚀 🌈我们上一篇…...
ROS使用(5)action学习
action消息的构建 首先进行功能包的创建 mkdir -p ros2_ws/src cd ros2_ws/src ros2 pkg create action_tutorials_interfaces action消息的类型 # Request --- # Result --- # Feedback 动作定义由三个消息定义组成,以---分隔。 从动作客户机向动作服务器发送…...
2023前端面试题集(含答案)之HTML+CSS篇(一)
在又到了金三银四的招聘季,不管你是刚入行的小白,亦或是混迹职场的老鸟,还在为面试前端工程师时不知道面试官要问什么怎么回答而苦恼吗?为了帮助你获得面试官的青睐,顺利通过面试,跳槽进入大厂,…...
设计模式2 - 观察者模式
定义: 观察者模式又叫发布订阅模式,它定义了对象之间的一对多依赖,这样一来,当一个对象改变状态时,它的所有依赖者都会收到通知并自动更新。 组成: Subject(通知者/被观察者)&#…...
ini配置文件
ini配置文件 ini文件是initialization file的缩写,即初始化文件,是widows系统配置文件所采用的存储格式。 文件扩展名: .ini ini配置文件的后缀名也不一定必须是.ini, 也可以是.cfg, .conf或者是.txt ini文件格式 ini配置文件由参数, 节, 注解组成 参…...
蓝桥杯备赛经验 pythonA组(非科班选手)
个人2022 CA组江苏省一等奖,决赛成绩不理想,没有拿到一二等奖,但是因为自己是非科班的学生,所以能拿到这样的成绩自己其实也应该知足了 题外话: 很多ACMer嘲笑蓝桥杯非常水,但是据我观察CA组决赛一等奖获奖…...
C++实现通讯录管理系统
通讯录是一个可以记录亲人、好友信息的工具,本博客借助黑马程序员的项目进行修改,利用C实现一个通讯录管理系统,旨在复习C的语法。 一、系统需求 系统需要实现的功能如下: 添加联系人∶向通讯录中添加新人,信息包括…...
Qwen3.5-2B镜像免配置部署:开箱即用WebUI(7860端口)快速上手教程
Qwen3.5-2B镜像免配置部署:开箱即用WebUI(7860端口)快速上手教程 1. 模型简介 Qwen3.5-2B是通义千问系列中的轻量化多模态基础模型,仅有20亿参数规模,专为低功耗、低门槛部署场景设计。这个版本特别适合在端侧设备和…...
DS4Windows手柄适配工具全解析:从安装到高级配置的完美指南
DS4Windows手柄适配工具全解析:从安装到高级配置的完美指南 【免费下载链接】DS4Windows Like those other ds4tools, but sexier 项目地址: https://gitcode.com/gh_mirrors/ds/DS4Windows 在PC游戏领域,手柄支持一直是玩家体验的关键环节。许多…...
Linux内核container_of宏解析与应用
1. 理解container_of宏的核心作用在Linux内核开发中,container_of宏是一个极其重要且频繁使用的工具。它的核心功能是通过结构体成员的地址反推出整个结构体的起始地址。想象一下,你手里只有一张照片的某个局部,却能准确找到这张照片在相册中…...
音频驱动面部动画:Audio2Face技术原理与实践指南
音频驱动面部动画:Audio2Face技术原理与实践指南 【免费下载链接】FACEGOOD-Audio2Face http://www.facegood.cc 项目地址: https://gitcode.com/gh_mirrors/fa/FACEGOOD-Audio2Face 在虚拟人技术快速发展的今天,面部动画的自然度成为提升用户体验…...
QQ空间记忆备份终极指南:3步永久保存你的数字青春
QQ空间记忆备份终极指南:3步永久保存你的数字青春 【免费下载链接】GetQzonehistory 获取QQ空间发布的历史说说 项目地址: https://gitcode.com/GitHub_Trending/ge/GetQzonehistory 你是否担心那些珍贵的QQ空间说说会随着时间消失?那些记录着青春…...
生成单颗10mm级配的cluster骨料
PFC5.0代码,可以破碎的cluster,可模拟碎石、矿渣混凝土材料,ball与cluster颗粒,单轴压缩实验,内涵声发射事件数代码,分析统计ball与ball直接的裂纹数目,cluster内部破碎的裂纹数目上周帮同门调P…...
桌面图标杂乱如何高效管理?NoFences开源工具让文件归类效率提升60%
桌面图标杂乱如何高效管理?NoFences开源工具让文件归类效率提升60% 【免费下载链接】NoFences 🚧 Open Source Stardock Fences alternative 项目地址: https://gitcode.com/gh_mirrors/no/NoFences 每天面对布满数十个图标的电脑桌面,…...
C++实战:高精度阶乘算法的实现与优化
1. 为什么我们需要高精度阶乘算法? 当你第一次学习编程时,可能会用循环或递归来实现阶乘计算。比如用C写个简单的for循环,轻松计算出5! 120。但当你尝试计算20!时,事情就开始变得有趣了——你会发现结果完全不对,甚至…...
别再只用labelme了!用ENVI 5.3的ROI工具给遥感影像打标签,效率翻倍
遥感影像标注革命:ENVI 5.3 ROI工具如何让深度学习标签制作效率提升300% 当无人机航拍的高清影像铺满整个屏幕,标注员的手指在鼠标和键盘间机械重复着点击、拖拽、保存的动作——这是许多刚接触遥感影像深度学习的研究者再熟悉不过的场景。传统标注工具在…...
Mathtype公式识别:Magma多模态AI在教育领域的应用
Mathtype公式识别:Magma多模态AI在教育领域的应用 1. 引言 作为一名长期关注AI技术发展的从业者,我最近在测试微软开源的Magma多模态模型时,发现了一个特别有意思的应用场景——数学公式识别与处理。想象一下这样的场景:老师批改…...
