移除元素(每日一题)

news/2024/10/30 21:26:18/

目录

一、题目描述

二、题目分析

2.1 方法一

2.1.1 思路

2.1.2 代码

2.2 方法二

2.2.1 思路

2.2.2 代码

一、题目描述

题目链接:27. 移除元素 - 力扣(LeetCode)

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

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

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

示例 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,4,0,3]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

二、题目分析

2.1 方法一

2.1.1 思路

     以空间换时间,本方法主要是在创建一个数组arr,用一个指针遍历原数组,将原数组中不等于val的值依次存放在arr数组中,然后将arr数组中的内容拷贝到原数组中。

     注意此方法的时间复杂度是:O(n),我们要对原数组遍历一遍,需要有一个循环,基本语句的执行次数是n次,此方法的空间复杂度是:O(n),由于在力扣环境中不支持C99中的变长数组,所以我们这里创建的数组个数按照题目中nums数组的最大个数来看,但是它的量级依然属于n。

2.1.2 代码

int removeElement(int* nums, int numsSize, int val) 
{int arr[100]={0};int src = 0;int dst = 0;while(src < numsSize){if (nums[src] == val){src++;}else{arr[dst++] = nums[src++];}}memcpy(nums,arr,dst*sizeof(int));return dst;
}

2.2 方法二

2.2.1 思路

     双指针,定义两个指针,src和dst,都从下标为0开始,如果src处的值不等于val,把它赋值到dst处,然后dst和src都加1,如果src处的值等于val,只对src加1,依次往后遍历,直到src=numsSize结束。

     此方法的时间复杂度为:O(n),其中 n 为序列的长度。我们只需要遍历该序列至多两次。空间复杂度是:O(1),我们只需要常数的空间保存若干变量。

2.2.2 代码

int removeElement(int* nums, int numsSize, int val) 
{int src = 0;int dst = 0;while (src < numsSize){if (nums[src] == val){src++;}else{nums[dst] = nums[src];dst++;src++;}}return dst;
}


http://www.ppmy.cn/news/29849.html

相关文章

python实现PCA降维画分类散点图并标出95%的置信区间

此代码以数据集鸢尾花为例&#xff0c;对其使用PCA降维后&#xff0c;绘制了三个类别的样本点和对应的置信圆&#xff08;即椭圆&#xff09;。先放效果图。 下面是完整代码&#xff1a; from matplotlib.patches import Ellipsedef plot_point_cov(points, nstd3, axNone, **…

Protobuf简介

Protobuf简介 1. Protocol Buffers1.1. 什么是Protocol Buffers?1.2. 选择你最喜欢的语言1.3. 如何开始2. Protocol Buffer Basics: C++2.1. 问题领域2.2. 在哪里找到示例代码2.3. 定义协议格式(Defining Your Protocol Format)1. Protocol Buffers Protocol Buffers(协议缓冲…

颠覆你的认知,业务同事都能开发软件,我简直无地自容……

经常看到网络鼓吹业务人员也能搭建应用&#xff0c;本是嗤之以鼻、半信半疑&#xff0c;但当这件事真实发生在自己身上时&#xff0c;竟觉得此言不虚&#xff1f; 一、背景 最近公司为了集成系统、提升扩展能力&#xff0c;引进了低代码平台JNPF&#xff0c;说个题外话&#…

基于容器云提交spark job任务

容器云提交spark job任务 容器云提交KindJob类型的spark任务&#xff0c;首先需要申请具有Job任务提交权限的rbac&#xff0c;然后编写对应的yaml文件&#xff0c;通过spark内置的spark-submit命令&#xff0c;提交用户程序(jar包)到集群执行。 1、创建任务job提交权限rbac …

C++11使用多线程(线程池)计算相似度实现性能优化

需求&#xff1a;图像识别中&#xff0c;注册的样本多了会影响计算速度&#xff0c;成为性能瓶颈&#xff0c;其中一个优化方法就是使用多线程。例如&#xff0c;注册了了3000个特征&#xff0c;每个特征4096个float。可以把3000个特征比对放到4个线程中进行计算&#xff0c;然…

lavis多模态开源框架学习--安装

安装lavis安装lavis测试安装问题过程中的其他操作安装lavis 因为lavis已经发布在pypi中&#xff0c;所以可以直接利用pip安装 pip install salesforce-lavis测试安装 from lavis.models import model_zoo print(model_zoo) # # Architectures Types # # …

【Java|golang】1487. 保证文件名唯一---golang中string方法的坑

给你一个长度为 n 的字符串数组 names 。你将会在文件系统中创建 n 个文件夹&#xff1a;在第 i 分钟&#xff0c;新建名为 names[i] 的文件夹。 由于两个文件 不能 共享相同的文件名&#xff0c;因此如果新建文件夹使用的文件名已经被占用&#xff0c;系统会以 (k) 的形式为新…

SpringBoot项目的快速创建方式(包含第一个程序的运行)

目录 一、IDEA所用的版本以及插件 二、操作步骤 一、IDEA所用的版本以及插件 idea的版本&#xff1a; idea2022版本下载安装配置与卸载详细步骤&#xff08;包含运行第一个java程序教程&#xff09;_idea2022下载_云边的快乐猫的博客-CSDN博客 如果英文看不懂就点击&#x1…