代码随想录二刷 | 数组 | 移除元素

代码随想录二刷 | 数组 | 移除元素

  • 题目描述
  • 解题思路 & 代码实现
    • 暴力解法
    • 双指针法

题目描述

27. 移除元素

给你一个数组 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

解题思路 & 代码实现

暴力解法

使用两层for循环,第一层遍历数组元素,第二层更新数组

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循环的工作。

  • 快指针:寻找新数组(即不含目标元素的数组)的元素
  • 慢指针:指向更新新数组下标的位置
class Solution {
public:
	int removeElement(vector<int> &nums, int val) {
		int slowIndex = 0;
		int size = nums.size();
		
		for (int fastIndex = 0; fastIndex < size; fastIndex++) {
			if (val != nums[fastIndex]) {
				nums[slowIndex++] = nums[fastIndex];
			}
		}
		return slowIndex;
	}
};

相对难理解的是这一句:

nums[slowIndex++] = nums[fastIndex];

它的意思是,当没有找到值为val的元素时(if语句的条件),将fastIndex指向的元素赋给slowIndex指向的元素,随后slowIndex向右移动一位。

它也等同于:

nums[slowIndex] = nums[fastIndex];
slowIndex++;

本题中双指针的目的是在原有数组的基础上重新构建一个不含目标值的新数组,删除操作被巧妙的隐藏在了构建新数组中。

如果一直没遇到目标值,每一次循环过后,两个指针是始终指向同一个元素的;如果遇到了目标值,slow指向的元素依然是非目标值元素,而fast指针会继续向前,在下一次飞目标值的循环时,slow指向的元素会重新获得fast指向的元素,也就是说,目标值没有被slow指向过,他不在新构建的数组中。

举一个例子来帮助理解:

一个数组如下,需要移除的元素是值等于val也就是等于2的元素,初始状态下fastIndex和slowIndex位置如下:
在这里插入图片描述
if (val != nums[fastIndex)的条件下,也就是下标0、1、2这三个位置:

  • fastIndex = 0,nums[fastIndex] = 1,nums[slowIndex] = nums[fastIndex],因此nums[slowIndex] = 1,slowIndex++,此时slowIndex = 1,循环体内结束,最后fastIndex++,fastIndex = 1.
  • fastIndex = 1,nums[fastIndex] = 3,nums[slowIndex] = nums[fastIndex],因此nums[slowIndex] = 3,slowIndex++,此时slowIndex = 2,循环体内结束,最后fastIndex++,fastIndex = 2.
  • fastIndex = 2,nums[fastIndex] = 3,nums[slowIndex] = nums[fastIndex],因此nums[slowIndex] = 3,slowIndex++,此时slowIndex = 3,循环体内结束,最后fastIndex++,fastIndex = 3.

此时的状态如下图:
在这里插入图片描述
此时遇到了目标值,不符合if的条件了,因此fastIndex会直接+1,fastIndex = 4,而slowIndex依然为2:
在这里插入图片描述
接下来的循环中,if条件又满足了,所以:
fastIndex=4,nums[fastIndex] = 1,nums[slowIndex] = nums[fastIndex],所以nums[slowIndex] = 1,slowIndex + 1 = 3。注意此时slowIndex指向了3,而nums[slowIndex] = 4,也就是说,原本的nums[3] = 2,变为了nums[slowIndex] = 1,就相当于删除了原本的nums[3] = 2。此时的数组如下图,可以看到nums[3] = 2 已经被替代了:

在这里插入图片描述
最后fastIndex+1 = 5,slowIndex = 3。接下来全部都符合if的条件,最后fastIndex来到末尾,整个程序结束。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

element表格头部加入图标

首先看看效果 下面是代码 <el-table-column prop"integralBalance"><template slot"header" slot-scope"scope"><div style"display: flex;justify-content: center;align-items: center;">积分余额<i class&qu…

2023年亚太杯数学建模思路 - 案例:异常检测

文章目录 赛题思路一、简介 -- 关于异常检测异常检测监督学习 二、异常检测算法2. 箱线图分析3. 基于距离/密度4. 基于划分思想 建模资料 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 一、简介 – 关于异常…

腾讯云重新注册算不算新用户?算!

腾讯云重新注册算新用户&#xff0c;但有以下限制&#xff1a; 首先&#xff0c;实名认证信息不能沿用老账号的信息&#xff0c;必须使用新的信息进行认证。这是为了确保重新注册的账号能够被视为新用户&#xff0c;并享受到新用户的特权和优惠。 腾讯云双十一领9999代金券 h…

2023亚太杯数学建模思路 - 案例:异常检测

文章目录 赛题思路一、简介 -- 关于异常检测异常检测监督学习 二、异常检测算法2. 箱线图分析3. 基于距离/密度4. 基于划分思想 建模资料 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 一、简介 – 关于异常…

java的包装类

目录 1. 包装类 1.1 基本数据类型和对应的包装类 1.2 装箱和拆箱 1.3 自动装箱和自动拆箱 1. 包装类 在Java中&#xff0c;由于基本类型不是继承自Object&#xff0c;为了在泛型代码中可以支持基本类型&#xff0c;Java给每个基本类型都对应了 一个包装类型。 若想了解…

k8s上Pod生命周期、重启策略、容器探测简介

目录 一.Pod的创建过程 二.Pod的终止过程 三.Pod的重启策略&#xff08;restartPolicy&#xff09; 1.Always 2.OnFailture 3.Never 4.示例 四.Pod生命周期内的5种状态&#xff08;相位&#xff09; 1.Pending 2.Running 3.Succeeded 4.Failed 5.Unknown 五.初始…

centos7安装mongodb

1、下载mongodb https://www.mongodb.com/try/download/community 2、解压 3、重命名 4、创建mongodb的data、logs目录 5、启动mongodb, bin/mongod --port27017 --dbpath/data/program/mongodb/data --logpath/data/program/mongodb/logs/mongodb.log --bind_ip0.0.0.0 --f…

上网行为审计软件能审计到什么

上网行为审计软件是一种用于监控和分析员工在工作时间使用互联网行为的软件工具。这种软件可以帮助企业管理员工在工作时间内的互联网使用情况&#xff0c;以确保员工的行为符合企业规定和法律法规。 域之盾软件---上网行为审计软件可以审计到以下内容&#xff1a; 1、网络访问…

3D建模基础教程:可编辑多边形建模的基础认识

可编辑多边形建模是3D建模中的一种常见方法&#xff0c;它允许用户对模型进行细致的调整和编辑。以下是对可编辑多边形建模的详细介绍&#xff1a; 1、层级概念&#xff1a;在可编辑多边形建模中&#xff0c;有五个层级&#xff0c;分别是点层级、边层级、边界层级、面层级和元…

数字化领导者圆桌对话:创造价值,助力企业数字化经营

近日&#xff0c;神策 2023 数据驱动大会成功举办。 数字化领导者圆桌对话环节&#xff0c;神策数据品牌事业部总经理刘洋、线性资本董事总经理郑灿、前波士顿咨询董事合伙人 & 中国知识开源计划首席布道师陈果与神策数据创始人 & CEO 桑文锋围绕科技创新、营销科技、业…

CCF ChinaSoft 2023 论坛巡礼|软件测试产教研融合论坛

2023年CCF中国软件大会&#xff08;CCF ChinaSoft 2023&#xff09;由CCF主办&#xff0c;CCF系统软件专委会、形式化方法专委会、软件工程专委会以及复旦大学联合承办&#xff0c;将于2023年12月1-3日在上海国际会议中心举行。 本次大会主题是“智能化软件创新推动数字经济与社…

观测云助力跨境电商大幅提高加载性能

话不多说&#xff0c;先上结果 什么是用户体验 用户体验基本包含访问网站的性能、可用性和正确性。通俗的讲&#xff0c;就是一把通过用户访问测量【设计者】意图的尺子。 用户体验的基本价值 如果正确实施了终端用户体验&#xff0c;可以第一时间发现&#xff0c;确认影响了…

ROS基础—关于参数服务器的操作

1、rosparam list 获取参数服务器的所有参数。 2、rosparam get /run_id 获取参数的值

【数据结构(二)】队列(2)

文章目录 1. 队列的应用场景和介绍1.1. 队列的一个使用场景1.2. 队列介绍 2. 数组模拟队列2.1. 思路分析2.2. 代码实现 3. 数组模拟环形队列3.1. 思路分析3.2. 代码实现 1. 队列的应用场景和介绍 1.1. 队列的一个使用场景 银行排队的案例&#xff1a; 1.2. 队列介绍 队列是一…

强化学习各种符号含义解释

&#xff1a;状态 : 动作 : 奖励 : 奖励函数 : 非终结状态 : 全部状态&#xff0c;包括终结状态 : 动作集合 ℛ : 奖励集合 : 转移矩阵 : 离散时间步 &#xff1a; 回合内最终时间步 : 时间t的状态 : 时间t动作 : 时间t的奖励,通常为随机量&#xff0c;且由和决定 : 回报 : n步…

虚拟机上安装docker,并安装flink镜像

1. 安装docker 官网步骤&#xff1a;https://docs.docker.com/engine/install/centos/ sudo yum install -y yum-utils sudo yum-config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo yum install docker-ce docker-ce-cli containerd.…

珠海希雷伺服全套(包含算法)方案

下载链接&#xff01;&#xff01;https://mp.weixin.qq.com/s?__bizMzU2OTc4ODA4OA&mid2247555038&idx1&sn939a4ad71582abc1f9e93c4d5526fed9&chksmfcfb0409cb8c8d1f74ce7108e20b0310e7399775367a023638624357644dfa4ae435e41c8768&token207079769&l…

【C++】类与对象 III 【 深入浅出理解 类与对象 】

文章内容 前言 &#xff1a;新关键字explicit 的引入一、explicit关键字二、static成员&#xff08;一&#xff09;概念&#xff08;二&#xff09;特性 三、匿名对象四、友元前言&#xff1a;友元的引入&#xff08;一&#xff09;友元的概念友元分为&#xff1a;友元函数 和 …

【django+vue】项目搭建、解决跨域访问

笔记为自我总结整理的学习笔记&#xff0c;若有错误欢迎指出哟~ 【djangovue】项目搭建、解决跨域访问 djangovue介绍vue环境准备vue框架搭建1.创建vue项目2.配置vue项目3.进入项目目录4.运行项目5.项目文件讲解6.vue的扩展库或者插件 django环境准备django框架搭建1.使用conda…

算法通关村第十关-白银挑战数组最大K数

大家好我是苏麟 , 今天带来一道应用快排的题 . 数组中的第K个最大元素 描述 : 给定整数数组 nums 和整数 k&#xff0c;请返回数组中第 k 个最大的元素。 请注意&#xff0c;你需要找的是数组排序后的第 k 个最大的元素&#xff0c;而不是第 k 个不同的元素。 题目 : Le…