当前位置: 首页 > news >正文

力扣经典150题第二题:移除元素

移除元素问题详解与解决方法

1. 介绍

移除元素问题是 LeetCode 经典题目之一,要求原地修改输入数组,移除所有数值等于给定值的元素,并返回新数组的长度。

问题描述

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

示例 1:

输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。
示例 2:

输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,3,0,4]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示:

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

2. 解题思路

方法一:双指针法

利用双指针技巧,一个指针 slow 在前,一个指针 fast 在后,当 fast 指向的元素等于给定值时,将 fast 指针后移;当 fast 指向的元素不等于给定值时,将 fast 指向的元素复制到 slow 指向的位置,并同时移动 slowfast 指针。

方法二:快慢指针法

维护一个下标 index,初始值为 0,遍历数组,如果当前元素不等于给定值,则将其复制到 index 位置,并将 index 后移。

方法三:交换移除法

维护两个指针 leftright,分别指向数组的首尾,当 nums[left] 等于给定值时,将 nums[left]nums[right] 交换,并将 right 指针左移;否则,将 left 指针右移。

3. 算法实现

方法一实现代码
public int removeElement(int[] nums, int val) {int slow = 0;for (int fast = 0; fast < nums.length; fast++) {if (nums[fast] != val) {nums[slow++] = nums[fast];}}return slow;
}
方法二实现代码
public int removeElement(int[] nums, int val) {int index = 0;for (int num : nums) {if (num != val) {nums[index++] = num;}}return index;
}
方法三实现代码
public int removeElement(int[] nums, int val) {int left = 0;int right = nums.length - 1;while (left <= right) {if (nums[left] == val) {nums[left] = nums[right];right--;} else {left++;}}return left;
}

4. 复杂度分析

时间复杂度分析

三种方法的时间复杂度均为 O(n),其中 n 为数组的长度,因为需要遍历整个数组。

空间复杂度分析

三种方法的空间复杂度均为 O(1),因为只使用了常数个额外变量。

5. 测试与验证

测试用例设计
  • 输入数组为空
  • 输入数组中不存在给定值
  • 输入数组中所有元素均为给定值
  • 输入数组中部分元素为给定值
测试结果分析

根据不同的测试用例,分析三种方法的输出结果,验证算法的正确性。

6. 扩展

如何处理特殊情况和边界条件?
  • 考虑输入数组为空的情况,直接返回 0。
  • 考虑输入数组中不存在给定值的情况,直接返回原数组的长度。
  • 考虑输入数组中所有元素均为给定值的情况,直接返回 0。
如何优化算法以提高执行效率?
  • 方法一和方法二的效率相似,但方法一更加简洁易懂,方法二可以省略下标遍历。
  • 方法三在交换时可以减少元素移动次数,提高效率。
如何处理数组中可能存在的重复元素?
  • 可以根据需要选择保留或跳过重复元素。

7. 总结

移除元素问题是一个经典的数组操作问题,通过三种不同的解题思路和算法实现,可以有效地移除数组中指定的元素,并返回新数组的长度。通过本文的详细讲解,读者可以更好地理解这个问题,掌握解题的关键思路和技巧。

8. 参考文献

  • LeetCode 官方网站
  • 《算法导论》
  • 《程序员面试金典》

感谢阅读

期待下一篇…

相关文章:

力扣经典150题第二题:移除元素

移除元素问题详解与解决方法 1. 介绍 移除元素问题是 LeetCode 经典题目之一&#xff0c;要求原地修改输入数组&#xff0c;移除所有数值等于给定值的元素&#xff0c;并返回新数组的长度。 问题描述 给你一个数组 nums 和一个值 val&#xff0c;你需要 原地 移除所有数值等…...

55555555555555

欢迎关注博主 Mindtechnist 或加入【Linux C/C/Python社区】一起学习和分享Linux、C、C、Python、Matlab&#xff0c;机器人运动控制、多机器人协作&#xff0c;智能优化算法&#xff0c;滤波估计、多传感器信息融合&#xff0c;机器学习&#xff0c;人工智能等相关领域的知识和…...

用Skimage学习数字图像处理(018):图像形态学处理(上)

本节开始讨论图像形态学处理&#xff0c;这是上篇&#xff0c;将介绍与二值形态学相关的内容&#xff0c;重点介绍两种基本的二值形态学操作&#xff1a;腐蚀和膨胀&#xff0c;以及三种复合二值形态学操作&#xff1a;开、闭和击中击不中变换。 目录 9.1 基础 9.2 基本操作…...

MySQL中 in 和 exists 区别

在MySQL中&#xff0c;IN和EXISTS都是用于在子查询中测试条件的操作符&#xff0c;但它们在处理和效率上有一些重要的区别。MySQL中的in语句是把外表和内表作hash连接&#xff0c;⽽exists语句是对外表作loop循环&#xff0c;每次loop循环再对内表进⾏查询。⼤家⼀直认为exists…...

Java基础 - 代码练习

第一题&#xff1a;集合的运用&#xff08;幸存者&#xff09; public class demo1 {public static void main(String[] args) {ArrayList<Integer> array new ArrayList<>(); //一百个囚犯存放在array集合中Random r new Random();for (int i 0; i < 100; …...

【Redis】redis集群模式

概述 Redis集群&#xff0c;即Redis Cluster&#xff0c;是Redis 3.0开始引入的分布式存储方案。实际使用中集群一般由多个节点(Node)组成&#xff0c;Redis的数据分布在这些节点中。集群中的节点分为主节点和从节点&#xff1a;只有主节点负责读写请求和集群信息的维护&#…...

基于opencv的猫脸识别模型

opencv介绍 OpenCV的全称是Open Source Computer Vision Library&#xff0c;是一个跨平台的计算机视觉库。OpenCV是由英特尔公司发起并参与开发&#xff0c;以BSD许可证授权发行&#xff0c;可以在商业和研究领域中免费使用。OpenCV可用于开发实时的图像处理、计算机视觉以及…...

基于注意力整合的超声图像分割信息在乳腺肿瘤分类中的应用

基于注意力整合的超声图像分割信息在乳腺肿瘤分类中的应用 摘要引言方法 Segmentation information with attention integration for classification of breast tumor in ultrasound image 摘要 乳腺癌是世界范围内女性最常见的癌症之一。基于超声成像的计算机辅助诊断&#x…...

数据库重点知识(个人整理笔记)

目录 1. 索引是什么&#xff1f; 1.1. 索引的基本原理 2. 索引有哪些优缺点&#xff1f; 3. MySQL有哪几种索引类型&#xff1f; 4. mysql聚簇和非聚簇索引的区别 5. 非聚簇索引一定会回表查询吗&#xff1f; 6. 讲一讲前缀索引&#xff1f; 7. 为什么索引结构默认使用B…...

[技术闲聊]checklist

电路设计完成后&#xff0c;需要确认功能完整性&#xff0c;明确是否符合设计规格需求&#xff1b;需要确认电路设计是否功能符合但是系列项不符合设计规则&#xff0c;如果都没有问题&#xff0c;那么就可以发给layout工程师。 今天主要讲讲电路设计规则&#xff0c;涉及到一…...

力扣刷题 二叉树的迭代遍历

题干 给你二叉树的根节点 root &#xff0c;返回它节点值的 前序 遍历。 示例 1&#xff1a; 输入&#xff1a;root [1,null,2,3] 输出&#xff1a;[1,2,3]示例 2&#xff1a; 输入&#xff1a;root [] 输出&#xff1a;[]示例 3&#xff1a; 输入&#xff1a;root [1] 输…...

【二】Django小白三板斧

今日内容 静态文件配置 request对象方法初识 pycharm链接数据库&#xff08;MySQL&#xff09; django链接数据库&#xff08;MySQL&#xff09; Django ORM简介 利用ORM实现数据的增删查改 【一】Django小白三板斧 HttpResponse 返回字符串类型的数据 render 返回HTML文…...

MyBatis的基本应用

源码地址 01.MyBatis环境搭建 添加MyBatis的坐标 <!--mybatis坐标--><dependency><groupId>org.mybatis</groupId><artifactId>mybatis</artifactId><version>3.5.9</version></dependency><!--mysql驱动坐…...

Day80:服务攻防-中间件安全HW2023-WPS分析WeblogicJettyJenkinsCVE

目录 中间件-Jetty-CVE&信息泄漏 CVE-2021-34429(信息泄露) CVE-2021-28169(信息泄露) 中间件-Jenkins-CVE&RCE执行 cve_2017_1000353 CVE-2018-1000861 cve_2019_1003000 中间件-Weblogic-CVE&反序列化&RCE 应用金山WPS-HW2023-RCE&复现&上线…...

使用generator实现async函数

我们先来看一下async函数是怎么使用的 const getData (sec) > new Promise((resolve) > {setTimeout(() > resolve(sec * 2), sec * 1000);})// aim to get this asycnFun by generator async function asyncFun() {const data1 await getData(1);const data2 awa…...

go并发请求url

sync.WaitGroup写法 package mainimport ("database/sql""fmt""net/http""sync""time"_ "github.com/go-sql-driver/mysql" )func main() {//开始计时start : time.Now()//链接数据库&#xff0c;用户名&#xf…...

刷题之Leetcode704题(超级详细)

704. 二分查找 力扣题目链接(opens new window)https://leetcode.cn/problems/binary-search/ 给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;写一个函数搜索 nums 中的 target&#xff0c;如果目标值存在返回下标&am…...

leetcode热题100.前k个高频元素

作者&#xff1a;晓宜 &#x1f308;&#x1f308;&#x1f308; 个人简介&#xff1a;互联网大厂Java准入职&#xff0c;阿里云专家博主&#xff0c;csdn后端优质创作者&#xff0c;算法爱好者 ❤️❤️❤️ 你的关注是我前进的动力&#x1f60a; Problem: 347. 前 K 个高频元…...

LangChain Demo | Agent X ReAct X wikipedia 询问《三体》的主要内容

背景 LangChain学习中&#xff0c;尝试改了一下哈里森和吴恩达课程当中的问题&#xff0c;看看gpt-3.5-turbo在集成了ReAct和wikipedia后&#xff0c;如何回答《三体》的主要内容是什么这个问题&#xff0c;当然&#xff0c;主要是为了回答这问题时LangChain内部发生了什么。所…...

Revit 2025新功能一览~

Hello大家好&#xff01;我是九哥~ Revit2025已经更新&#xff0c;安装后&#xff0c;简单试了下&#xff0c;还是挺不错的&#xff0c;流畅度啊&#xff0c;新功能啊&#xff0c;看来还是有听取用户意见的&#xff0c;接下来就简单看看都有哪些新功能。 好了&#xff0c;今天的…...

Head First Design Patterns -代理模式

什么是代理模式 代理模式为另一个对象提供替身或者占位符&#xff0c;以便控制客户对对象的访问&#xff0c;管理访问的方式有很多种。例如远程代理、虚拟代理、保护代理等。 远程代理&#xff1a;管理客户和远程对象之间的交互。 虚拟代理&#xff1a;控制访问实例化开销大的对…...

第十三题:天干地支

题目描述 古代中国使用天干地支来记录当前的年份。 天干一共有十个&#xff0c;分别为&#xff1a;甲&#xff08;jiǎ&#xff09;、乙&#xff08;yǐ&#xff09;、丙&#xff08;bǐng&#xff09;、丁&#xff08;dīng&#xff09;、戊&#xff08;w&#xff09;、己&a…...

8000预算可以购买阿里云服务器配置整理

一个月8000元预算如何选择阿里云服务器配置&#xff1f;八千预算可选的阿里云服务器配置相当高了&#xff0c;这个预算可以购买阿里云企业级独享型云服务器&#xff0c;至少8核以上的配置&#xff0c;这个预算可以支持复杂、高负载或大规模的业务需求。阿里云服务器网整理8000元…...

游戏APP如何提高广告变现收益的同时,保证用户留存率?

APP广告变现对接第三方聚合广告平台主要通过SDK文档对接&#xff0c;一些媒体APP不具备专业运营广告变现的对接能力和资源沉淀&#xff0c;导致APP被封控&#xff0c;设置列入黑名单&#xff0c;借助第三方聚合广告平台进行商业化变现是最佳选择。#APP广告变现# 接入第三方平台…...

Linux ulimit命令教程:如何查看和设置系统资源限制(附实例详解和注意事项)

Linux ulimit命令介绍 ulimit是一个内置的Linux shell命令&#xff0c;它允许查看或限制单个用户可以消耗的系统资源量。在有多个用户和系统性能问题的环境中&#xff0c;限制资源使用是非常有价值的。 Linux ulimit命令适用的Linux版本 ulimit命令在所有主流的Linux发行版中…...

(delphi11最新学习资料) Object Pascal 学习笔记---第8章第5节(封闭类和Final方法)

8.5.2 封闭类和Final方法 如前所述&#xff0c;Java 采用非常动态的方法&#xff0c;默认情况下采用延迟绑定&#xff08;或虚函数&#xff09;。因此&#xff0c;Java 语言引入了一些概念&#xff0c;如不能继承的类&#xff08;封闭类&#xff09;和不能在派生类中覆盖的方法…...

vue3从精通到入门12:vue3的生命周期和组件

生命周期&#xff1a; 生命周期钩子主要包括&#xff1a; beforeCreate&#xff1a;组件实例被创建之前调用。在这个阶段&#xff0c;组件的 props 和 data 还未被初始化。created&#xff1a;组件实例创建完成后调用。在这个阶段&#xff0c;组件的 props 和 data 已经被初始…...

力扣热题100_链表_21_合并两个有序链表

文章目录 题目链接解题思路解题代码 题目链接 21. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1&#xff1a; 输入&#xff1a;l1 [1,2,4], l2 [1,3,4] 输出&#xff1a;[1,1,2,3,4,4] 示例…...

探索未来智慧酒店网项目接口架构

在数字化时代&#xff0c;智慧酒店已成为酒店业发展的重要趋势之一。智慧酒店网项目接口架构作为支撑智慧酒店运营的核心技术之一&#xff0c;其设计和优化对于提升用户体验、提高管理效率具有重要意义。本文将深入探讨智慧酒店网项目接口架构的设计理念和关键要素。 ### 智慧…...

os模块篇(十三)

文章目录 os.mknod(path, mode0o600, device0, *, dir_fdNone)os.major(device, /)os.minor(device, /)os.makedev(major, minor, /)os.pathconf(path, name)os.readlink(path, *, dir_fdNone)os.remove(path, *, dir_fdNone)os.removedirs(name)os.rename(src, dst, *, src_di…...

建网站 企汇网/怎样做搜索引擎推广

PopupWindow就是弹出窗口的意思&#xff0c;类似windows下面的开始按钮。PopupWindow可以实现浮层效果&#xff0c;而且可以自定义显示位置&#xff0c;出现和退出时的动画.今天写了一个效果&#xff0c;希望可以帮助到大家. 下面我们来看看效果图吧&#xff1a; 1.因为我的项目…...

给自己的网站做软件测试 步骤/优化服务内容

正题第四题&#xff1a;[SDOI2009]Elaxia的路线这道题好像很麻烦。。。首先我们可以知道&#xff0c;如果边(x,y,c)为x1到y1最短路路径上的一条边&#xff0c;那么它肯定满足d[x1][x]d[y][y1]cd[x][y] || d[x1][y]d[x][y1]cd[x][y]那么知道了这个东西&#xff0c;我…...

wap网站建设服务/推广普通话宣传语100字

SpringMVC是什么 SpringMVC是目前最好的实现MVC设计模式的框架&#xff0c;是Spring框架的一个分支产品&#xff0c;以SpringIOC容器为基础&#xff0c;并利用容器的特性来简化它的配置。SpringMVC相当于Spring的一个子模块&#xff0c;可以很好的和Spring结合起来进行开发&…...

不用vip的免费追剧软件/防城港网站seo

每次使用etcdctl&#xff0c;都要长长的一大串&#xff0c;太麻烦了&#xff0c;直接把变量写入文件中&#xff0c;就方便很多了 vi ~/.bashrc 行尾添加 export ETCDCTL_ENDPOINTShttps://127.0.0.1:2379export ETCDCTL_CACERT/etc/kubernetes/pki/etcd/ca.crtexport ETCDCTL_C…...

南宁网站建设公司哪家好/网站seo博客

框架搭建设想框架:在VS2010 下的项目管理流程RoadMarkingDetection&#xff1a;工程项目入口&#xff0c;启动项目&#xff0c;配置类型Configuration Type 为Application(.exe)可以调用以下所有模块&#xff08;.lib&#xff09;。commonClass&#xff1a;保存全局数据类、工具…...

删除wordpress文章日期/百度关键词推广方案

一、目的 减少操作系统安装过程中人机交互过程&#xff0c;实现选择光盘安装后&#xff0c;无需其他人机交互过程即可自动完成操作系统的安装。 二、环境和软件工具 环境&#xff1a;Linux Ubuntu/CentOS操作系统&#xff08;其他发行版未作尝试&#xff09; 软件&#xff…...