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

Leetcode—移除元素、删除有序数组中的重复项、合并两个有序数组

移除元素

在这里插入图片描述
此题简单,用双指针方法即可,
如果右指针指向的元素不等于val,它一定是输出数组的一个元素,我们就将右指针指向的元素复制到左指针位置,然后将左右指针同时右移;
如果右指针指向的元素等于 val,它不能在输出数组里,此时左指针不动,右指针右移一位。
在这里插入图片描述

且最后需要输出的数组长度就是left的值。不多说,上代码:

int removeElement(int* nums, int numsSize, int val)
{int left =0;int right =0;for(int i =0;i<numsSize;i++){if(nums[right] != val){nums[left]=nums[right];++left;++right;}else{++right;}}return left;}

时间复杂度:O(N)
空间复杂度:O(1)

删除有序数组中的重复项

在这里插入图片描述

暴力想法

(注意是暴力想法,不是暴力解法!)
作为直男直接就是想实现。
直接遍历,看题目是已经确定了是有序的,遇到与上一个不相等的直接给他拿到新的数组里面存起来。遍历完直接新数组就是答案。
看样子是很接近了哈!毕竟属于简单的题目。但是, O(1) 额外空间的条件下完成这个是我们跨不过去的坎。既然如此那就得考虑在原数组上操作。

双指针法

定义两个指针fast 和 slow 分别为快指针和慢指针,快指针表示遍历数组到达的下标位置,慢指针表示下一个不同元素要填入的下标位置,初始时两个指针都指向下标 1。
假设数组nums 的长度为 n。将快指针 fast 依次遍历从 1 到 n-1 的每个位置,对于每个位置,如果nums[fast] !=nums[fast-1],说明 nums[fast] 和之前的元素都不同,因此将 nums[fast] 的值复制到nums[slow],然后将 slow 的值加 1,即指向下一个位置。遍历结束之后,从 nums[0] 到 nums[slow−1] 的每个元素都不相同且包含原数组中的每个不同的元素,因此新的长度即为 slow,返回 slow 即可。
在这里插入图片描述

//C
int removeDuplicates(int* nums, int numsSize)
{int right =1;int left =1;for(int i=1;i<numsSize;i++){if(nums[right-1]!=nums[right]){nums[left]=nums[right];++left;++right;}else{++right;}}return left;
}

合并两个有序数组

在这里插入图片描述

方法一:直接合并后排序

最直观的方法是先将数组 nums 2放进数组nums 1的尾部,然后直接对整个数组进行排序。

int cmp(int* a, int* b) {return *a - *b;
}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {for (int i = 0; i != n; ++i) {nums1[m + i] = nums2[i];}qsort(nums1, nums1Size, sizeof(int), cmp);
}

时间复杂度:O((m+n)\log(m+n))
空间复杂度:O(log(m+n))

方法二:逆向双指针

观察可知,nums 1 的后半部分是空的,可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历,每次取两者之中的较大者放进 nums 1的最后面。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int end1 =m-1;int end2 = n -1;int end = m+n-1;while(end1 >= 0 && end2 >= 0){if(nums1[end1]>nums2[end2]){nums1[end--]=nums1[end1--];}else{nums1[end--]=nums2[end2--];}}while(end2 >=0){nums1[end--] = nums2[end2--];}}

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

相关文章:

Leetcode—移除元素、删除有序数组中的重复项、合并两个有序数组

移除元素 此题简单&#xff0c;用双指针方法即可&#xff0c; 如果右指针指向的元素不等于val&#xff0c;它一定是输出数组的一个元素&#xff0c;我们就将右指针指向的元素复制到左指针位置&#xff0c;然后将左右指针同时右移&#xff1b; 如果右指针指向的元素等于 val&…...

面试(十)大疆 安全开发 C++1面

1. 在C++开发中定义一个变量,若不做初始化直接使用会怎样? 如果该变量是一个普通变量,则如果对其进行访问,会返回一个随机值,int类型不一定为0,bool类型也不一定为false 如果该变量为一个静态变量,则初始值都是一个0; 如果该变量是一个指针,那么在后续程序运行中很…...

短信链接跳转微信小程序

短信链接跳转微信小程序1 实现方案1.1 通过URL Scheme实现1.2 通过URL Link实现1.3 通过云开发静态网站实现2 实现方案对比3 实践 URL Schema 方案3.1 获取微信access_token3.2 获取openlink3.3 H5页面&#xff08;模拟短信跳转&#xff0c;验证ok&#xff09;4 问题小节4.1 io…...

吉林电视台启用乾元通多卡聚合系统广电视频传输解决方案

随着广播电视数字化、IP化、智能化的逐步深入&#xff0c;吉林电视台对技术改造、数字设备升级提出了更高要求&#xff0c;通过对系统性能、设计理念的综合评估&#xff0c;正式启用乾元通多卡聚合系统广电视频传输解决方案&#xff0c;将用于大型集会、大型演出、基层直播活动…...

Linux常用命令1

目录1、远程登陆服务器2、文件相关&#xff08;1&#xff09;文件和目录属性&#xff08;2&#xff09;创建目录mkdir&#xff08;3&#xff09;删除目录rmdir&#xff08;4&#xff09;创建文件touch&#xff08;5&#xff09;删除文件或目录rm&#xff08;6&#xff09;ls命令…...

【C++进阶】一、继承(总)

目录 一、继承的概念及定义 1.1 继承概念 1.2 继承定义 1.3 继承基类成员访问方式的变化 二、基类和派生类对象赋值转换 三、继承中的作用域 四、派生类的默认成员函数 五、继承与友元 六、继承与静态成员 七、菱形继承及菱形虚拟继承 7.1 继承的分类 7.2 菱形虚拟…...

AttributeError: module ‘lib‘ has no attribute ‘OpenSSL_add_all_algorithms

pip安装crackmapexec后,运行crackmapexec 遇到报错 AttributeError: module lib has no attribute OpenSSL_add_all_algorithms 直接安装 pip3 install crackmapexec 解决 通过 python3 -m pip install --upgrade openssl 或者 python3 -m pip install openssl>22.1.…...

Python实现视频自动打码功能,避免看到羞羞的画面

前言 嗨呀嗨呀&#xff0c;最近重温了一档综艺节目 至于叫什么 这里就不细说了 老是看着看着就会看到一堆马赛克&#xff0c;由于太好奇了就找了一下原因&#xff0c;结果是因为某艺人塌房了…虽然但是 看综艺的时候满影响美观的 咳咳&#xff0c;这里我可不是来教你们如何解…...

说说Knife4j

Knife4j是一款基于Swagger2的在线API文档框架使用Knife4j, 需要 添加Knife4j的依赖当前建议使用的Knife4j版本, 只适用于Spring Boot2.6以下版本, 不含Spring Boot2.6 在主配置文件(application.yml)中开启Knife4j的增强模式必须在主配置文件中进行配置, 不要配置在个性化配置文…...

Java学习笔记-03(API阶段-2)集合

集合 我们接下来要学习的内容是Java基础中一个很重要的部分&#xff1a;集合 1. Collection接口 1.1 前言 Java语言的java.util包中提供了一些集合类,这些集合类又称之为容器 提到容器不难想到数组,集合类与数组最主要的不同之处是,数组的长度是固定的,集合的长度是可变的&a…...

「3」线性代数(期末复习)

&#x1f680;&#x1f680;&#x1f680;大家觉不错的话&#xff0c;就恳求大家点点关注&#xff0c;点点小爱心&#xff0c;指点指点&#x1f680;&#x1f680;&#x1f680; 矩阵的秩 定义4:在mxn矩阵A中&#xff0c;任取k行与k列&#xff08;k<m,k<n&#xff09;,位…...

【CSDN竞赛】27期题解(Javascript)

前言 本来排名是20的&#xff0c;不过第一题有点输出bug&#xff0c;最后实际测出来又重新排名&#xff0c;刚好卡在第10。但是考试报告好像过了12小时就下载不到了&#xff0c;所以就只写题目求解的JS函数吧。 1. 幸运数字 小艺定义一个幸运数字的标准包含3条: 仅包含4或7幸…...

高压放大器在骨的逆力电研究中的应用

实验名称&#xff1a;高压放大器在骨的逆力电研究中的应用研究方向&#xff1a;生物医学测试目的&#xff1a;骨中的胶原和羟基磷灰石沿厚度分布不均匀&#xff0c;骨试样在直流电压作用下&#xff0c;内部出现传导电流引起试样内部温度升高&#xff0c;不同组分热变形不一致&a…...

思科网络部署,(0基础)入门实验,超详细

♥️作者&#xff1a;小刘在C站 ♥️个人主页&#xff1a;小刘主页 ♥️每天分享云计算网络运维课堂笔记&#xff0c;努力不一定有收获&#xff0c;但一定会有收获加油&#xff01;一起努力&#xff0c;共赴美好人生&#xff01; ♥️夕阳下&#xff0c;是最美的绽放&#xff0…...

private static final Long serialVersionUID= 1L详解

我们知道在对数据进行传输时&#xff0c;需要将其进行序列化&#xff0c;在Java中实现序列化的方式也很简单&#xff0c;可以直接通过实现Serializable接口。但是我们经常也会看到下面接这一行代码&#xff0c;private static final Long serialVersionUID 1L&#xff1b;这段代…...

若依前后端分离版集成nacos

根据公司要求&#xff0c;需要将项目集成到nacos中&#xff0c;当前项目是基于若依前后端分离版开发的&#xff0c;若依的版本为3.8.3&#xff0c;若依框架中整合的springBoot版本为2.5.14。Nacos核心提供两个功能&#xff1a;服务注册与发现&#xff0c;动态配置管理。 一、服…...

JAVA面试八股文一(mysql)

B-Tree和BTree区别共同点&#xff1b;一个节点可以有多个元素&#xff0c; 排好序的不同点&#xff1a;BTree叶子节点之间有指针&#xff0c;非叶子节点之间的数据都冗余了一份在叶子节点BTree是B-Tree 的升级mysql什么情况设置了索引&#xff0c;但无法使用a.没符合最左原则b.…...

动静态库概念及创建

注意在库中不能写main()函数。 复习gcc指令 预处理-E-> xx.i 编译 -S-> xx.s 汇编 -c-> xx.o 汇编得到的 xx.o称为目标可重定向二进制文件&#xff0c;此时的文件需要把第三方库链接进来才变成可执行程序。 gcc -o mymath main.c myadd.c mysub.c得到的mymath可以执…...

【H.264】码流解析 annexb vs avcc

H264码流解析及NALUAVCC和ANNEXB 前者是FLV容器、mp4 常用的。后者 是实时传输使用,所以是TS 一类的标准。VLC显示AVC1就是AVCC AVCC格式 也叫AVC1格式,MPEG-4格式,字节对齐,因此也叫Byte-Stream Format。用于mp4/flv/mkv, VideoToolbox。 – Annex-B格式 也叫MPEG-2 trans…...

【最优化方法】1-最优化方法介绍

文章目录1 最优化起源2 最优化发展3 运筹学在国外4 运筹学在国内5 什么是最优化&#xff1f;6 为什么要研究最优化问题&#xff1f;7 最优化问题8 最优化问题分类9 最优化研究内容理论算法应用1 最优化起源 中国古代优化思想–田忌赛马(公元前340年) 18世纪L.Euler&#xff0…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#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"…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...