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

leetcode经典面试150题---2.移除元素

题目描述


给你一个数组 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。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

说明:

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

前置知识


  • 双指针

代码


方法一 双指针

思路

  • 我们可以将数组分成「前后」两段:
  • 前半段是有效部分,存储的是不等于 val 的元素。
  • 后半段是无效部分,存储的是等于 val 的元素。
  • 最终答案返回有效部分的结尾下标。

实现

class Solution {public int removeElement(int[] nums, int val) {int j = nums.length - 1;for (int i = 0; i <= j; i++) {if (nums[i] == val) {swap(nums, i--, j--);}}return j + 1;}void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

复杂度

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

方法二  通用解法

思路

  • 先设定变量 idx,指向待插入位置。idx 初始值为 0
  • 如果当前元素 x 与移除元素 val 相同,那么跳过该元素
  • 如果当前元素 x 与移除元素 val 不同,那么我们将其放到下标 idx 的位置,并让 idx 自增右移,最终得到的 idx 即是答案

实现

class Solution {public int removeElement(int[] nums, int val) {int idx = 0;for (int x : nums) {if (x != val) nums[idx++] = x;}return idx;}
}

 

复杂度

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

相关文章:

leetcode经典面试150题---2.移除元素

题目描述 给你一个数组 nums 和一个值 val&#xff0c;你需要 原地 移除所有数值等于 val 的元素&#xff0c;并返回移除后数组的新长度。 不要使用额外的数组空间&#xff0c;你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新…...

【尘缘赠书活动:01期】Python数据挖掘——入门进阶与实用案例分析

引言 本案例将根据已收集到的电力数据&#xff0c;深度挖掘各电力设备的电流、电压和功率等情况&#xff0c;分析各电力设备的实际用电量&#xff0c;进而为电力公司制定电能能源策略提供一定的参考依据。更多详细内容请参考**《Python数据挖掘&#xff1a;入门进阶与实用案例…...

计算机网络(谢希仁)第八版课后题答案(第二章)

1.物理层要解决哪些问题&#xff1f;物理层的主要特点是什么&#xff1f; (1)物理层要尽可能地屏蔽掉物理设备和传输媒体&#xff0c;通信手段的不同&#xff0c;使数据链路层感觉不到这些差异&#xff0c;只考虑完成本层的协议和服务。 (2)给其服务用户&#xff08;数据链路…...

搭建nuxt3项目(框架构建)

需求 目标&#xff1a;我想搭建一个nuxt3的框架&#xff0c;实现一些基本的组件和路由、页面&#xff0c;方便后续遇到相关ssr项目直接复用。 同时&#xff1a;记录关于nuxt3的使用介绍关于Nuxt&#xff08;详解以及周边&#xff09; Nuxt 框架 1、一种基于 Node.js 的服务端…...

系统架构设计之微内核架构(Microkernel Architecture)

微内核架构&#xff08;Microkernel Architecture&#xff09; 一. 什么是微内核架构二. 微内核架构风格-拓扑结构三. 微内核的核心系统设计的三个关键点3.1 插件管理3.2 插件连接3.3 插件通信 四. 微内核架构的优缺点 一. 什么是微内核架构 微内核架构是一种面向功能进行拆分的…...

51单片机实现换能器超声波测水深

一&#xff0c;超声波换能器定义&#xff1a; 定义1&#xff1a;可把电能、机械能或声能从一种形式转换为另一种形式的能的装置。 所属学科&#xff1a;测绘学下的测绘仪器。 定义2&#xff1a;能量转换的器件。在水声领域中常把声呐换能器、水声换能器、电声换能器统称换能器。…...

Spring Cloud Config

Spring Cloud Config 服务端:一个集中化配置中心,可以是一个独立的服务,也可以注册到服务治理中心,它可以集中管理各个 微服务的配置; 作用原理是从某个地方读取(本地/云端)提供给其客户端作为配置; 客户端:作为一个服务端,通过读取Config的服务端来获取自己的配置文件; 服务…...

易基因: Nature Biotech:番茄细菌性青枯病的噬菌体联合治疗|国人佳作

大家好&#xff0c;这里是专注表观组学十余年&#xff0c;领跑多组学科研服务的易基因。 生物防治是利用细菌接种剂来改变植物根际微生物群落的组成&#xff0c;但在以往研究中存在有接种的细菌在根际建立不良&#xff0c;与本地微生物组争夺资源&#xff0c;干扰本地微生物的…...

震坤行亮相2023工博会,并荣获第23届中国工博会“CIIF信息技术奖”

震坤行亮相2023工博会&#xff0c;并荣获第23届中国工博会“CIIF信息技术奖” 2023年9月19日&#xff0c;2023年第23届中国国际工业博览会CIIF&#xff08;以下简称“工博会”&#xff09;在上海国家会展中心盛大开幕。震坤行紧跟智能制造产业发展步伐&#xff0c;携数字化解决…...

灯带代码实现

#include "FastLED.h" // FastLED库#define NUM_LEDS 60 // LED灯珠数量 #define DATA_PIN 3 // Arduino输出控制信号引脚 #define LED_TYPE WS2812 // LED灯带型号 #define COLOR_ORDER GRB // RGB灯珠中红色、…...

Monocular arbitrary moving object discovery and segmentation 论文阅读

基本信息 题目&#xff1a;Monocular Arbitrary Moving Object Discovery and Segmentation 作者&#xff1a; 来源&#xff1a;BMVC 时间&#xff1a;2021 代码地址&#xff1a;https://github.com/michalneoral/Raptor Abstract 我们提出了一种发现和分割场景中独立移动的…...

ROS | 命名空间

文章目录 概述一、定义介绍二、原理解读1.命名空间2.调用规则概述 本节详细介绍了ROS中的命名空间机制原理和使用。 一、定义介绍 在ROS(Robot Operating System)中,命名空间是一种用于组织和区分节点、话题、服务和参数等资源的层次结构。命名空间使用斜线(/)作为分隔符…...

【中国数据】中国基础矢量数据(shp格式)

数据目录 数据举例 数据获取 专栏分享常用的地理空间数据&#xff0c;包括矢量数据、栅格数据、统计数据等&#xff0c;订阅专栏后&#xff0c;从私信查收专栏完整数据包&#xff0c;持续同步更新。...

Docker:创建主从复制的Redis集群

一、Redis集群 在实际项目里&#xff0c;一般不会简单地只在一台服务器上部署Redis服务器&#xff0c;因为单台Redis服务器不能满足高并发的压力&#xff0c;另外如果该服务器或Redis服务器失效&#xff0c;整个系统就可能崩溃。项目里一般会用主从复制的模式来提升性能&#x…...

c++ 智能指针

1. 起源 c++ 把内存的控制权对开发人员开放,让程序显式的控制内存,这样能够快速的定位到占用的内存,完成释放的工作。但是这样也会引发一些问题,也就是普通指针的隐患: 1.1 野指针 出现野指针的有几个地方 : 指针声明而未初始化,此时指针的将会随机指向内存已经被释放…...

【vue3】依赖注 provide、inject(父组件与儿子、孙子、曾孙子组件之间的传值)

一、基本用法&#xff1a; //父组件 import { ref, provide } from vue const radio ref<string>(red) provide(myColor,radio) //注入依赖//儿子组件、孙子组件、曾孙子组件 import { inject } from vue import type { Ref } from vue; const myColor inject<Ref&l…...

docker 部署tig监控服务

前言 tig对应的服务是influxdb grafana telegraf 此架构比传统的promethus架构更为简洁&#xff0c;虽然influxdb开源方案没有集群部署&#xff0c;但是对于中小型服务监控需求该方案简单高效 本文以docker-compose来演示这套监控体系的快速搭建和效果。 部署 docker-compos…...

ETL工具与数据处理的关系

ETL工具与数据处理之间存在密切的关系。数据处理是指对原始数据进行清洗、整理、加工和分析等操作&#xff0c;以便生成有用的信息和洞察力。而ETL工具则提供了一种自动化和可视化的方式来执行这些数据处理任务。通过ETL工具&#xff0c;用户可以定义数据抽取、转换和加载的规则…...

Flink几个性能调优

1 配置内存 操作场景 Flink是依赖内存计算&#xff0c;计算过程中内存不够对Flink的执行效率影响很大。可以通过监控GC&#xff08;Garbage Collection&#xff09;&#xff0c;评估内存使用及剩余情况来判断内存是否变成性能瓶颈&#xff0c;并根据情况优化。 监控节点进程的…...

后端工程进阶| 青训营笔记

这是我参与「第五届青训营 」伴学笔记创作活动的第 2 天 并发编程 协程Goroutine通道Channel锁Lock 并发基础 串行程序与并发程序&#xff1a;串行程序特指只能被顺序执行的指令列表&#xff0c;并发程序则是可以被并发执行的两个及以上的串行程序的综合体。并发程序与并行程序…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...