力扣每日一道系列 --- LeetCode 88. 合并两个有序数组

文章目录
- 思路1:暴力求解
- 思路2:原地合并
LeetCode 88. 合并两个有序数组


思路1:暴力求解
- 首先创建一个临时数组,其大小为第一个数组的大小(即nums1Size),其作用主要是。
- 通过循环遍历两个数组,将两个数组元素比较后较小的元素依次加入到临时数组中,直到有一个数组遍历完即可(注意:这里遍历完是只有效元素被遍历完,因为nums1中有无效元素0)。
- 将未遍历完的数组剩下的元素依次加入到临时数组中。
- 将临时数组中的元素依次拷贝到nums1数组中。
- 释放临时数组的空间。
时间复杂度:O(m+n)
空间复杂度:O(m+n)
值得注意的是: 这里需要考略到两种特殊情况需要单独处理
nums2数组为空时,nums1数组就是两个数组排序后的结果,函数不需要执行任何操作,直接return即可nums1数组中有效的元素个数为0(即m = 0) 时,此时nums2数组中的元素就是两个数组排序后的结果,此时只需要将nums2中的数组元素拷贝到nums1数组即可。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){if(nums2==NULL){return;}else if(m==0){for(int i=0;i<nums1Size;i++){nums1[i]=nums2[i];}}//创建一个数组来临时存放排序之后的元素,元素个数为m+n = nums1Sizeint *arr = (int*)malloc((nums1Size)*sizeof(int));int index = 0,dest = 0,src = 0;//dest和src分别标记访问当前数组元素的下标//index标记临时数组加入元素的下标位置//依次遍历两个数组,直到有一个数组遍历完为止while(dest < m && src < n){if(nums1[dest]<=nums2[src]){arr[index++] = nums1[dest++];}else{arr[index++] = nums2[src++];}}//将未遍历完的数组剩下的元素加入到临时数组中if(src>=n){while(dest<m){arr[index++] = nums1[dest++];}}else if(dest>=m){while(src<n){arr[index++] = nums2[src++];}}//将临时数组中的元素依次赋值给nums1数组中对应位置的元素for(int i = 0;i<nums1Size;i++){nums1[i] = arr[i];}free(arr);//将创建的数组空间释放
}
思路2:原地合并
- 从后往前遍历数组,将
nums1和nums2中的元素逐个比较,将较大的元素往nums1末尾进行搬移- 第一步结束后,
nums2中可能会有数据没有搬移完,将nums2中剩余的元素逐个搬移到nums1- 如果
num1中剩余元素没有搬移完,就不需要进行任何操作,因为num1中剩余的元素本来就在num1中
时间复杂度:O(m+n)
空间复杂度:O(1)
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){// end1、end2:分别标记nums1 和 nums2最后一个有效元素位置// end标记nums1的末尾,因为nums1和nums2中的元素从后往前往nums1中存放// ,否则会存在数据覆盖int end1 = m-1;int end2 = n-1;int index = m+n-1;// 从后往前遍历,将num1或者nums2中较大的元素往num1中end位置搬移// 直到将num1或者num2中有效元素全部搬移完while(end1 >= 0 && end2 >= 0){if(nums1[end1] > nums2[end2]){nums1[index--] = nums1[end1--];}else{nums1[index--] = nums2[end2--];}}// num2中的元素可能没有搬移完,将剩余的元素继续往nums1中搬移while(end2 >= 0){nums1[index--] = nums2[end2--];}// num1中剩余元素没有搬移完 ---不用管了,因为num1中剩余的元素本来就在num1中
}
如果大家有什么疑问可以在评论区与我讨论,或者直接私信我,感谢大家的阅读哦 ~
相关文章:
力扣每日一道系列 --- LeetCode 88. 合并两个有序数组
📷 江池俊: 个人主页 🔥个人专栏: ✅数据结构探索 ✅LeetCode每日一道 🌅 有航道的人,再渺小也不会迷途。 文章目录 思路1:暴力求解思路2:原地合并 LeetCode 88. 合并两个有序数组…...
Android Studio(项目收获)
取消按钮默认背景色 像按钮默认背景色为深蓝色,即使使用了background属性指定颜色也不能生效。 参考如下的解决方法: 修改/res/values/themes.xml中的指定内容如下: <style name"Theme.TianziBarbecue" parent"Theme.Mater…...
MQ写满的情况如何处理?
**MQ(Message Queue)**写满的情况通常指消息队列中的存储空间已经被用尽,无法再接收新的消息。处理MQ写满的情况涉及到多个方面,包括监控、调整配置、增加资源、以及处理积压消息等。下面是一些处理MQ写满的 常见方法:…...
点名(缺失的数字),剑指offer,力扣
目录 我们直接看题解吧: 审题目事例提示: 方法: 解题思路(二分法): 代码: 方法二:直接遍历 题目地址 LCR 173. 点名 - 力扣(LeetCode) 今天刷点名(…...
云安全—Dashboard 攻击面
0x00 前言 众所周知,如果只是一味的REST接口或者命令行话的操作方式,就会变相的提高操作门款,并且不会有很好的呈现方式,所以就有了web ui的方式,也就是Dashboar面板,本篇主要讨论一下关于Dashboar面板的概…...
FCOS难点记录
FCOS 中有计算 特征图(Feature map中的每个特征点到gt_box的左、上、右、下的距离) 1、特征点到gt_box框的 左、上、右、下距离计算 x coords[:, 0] # h*w,2 即 第一列y coords[:, 1] l_off x[None, :, None] - gt_boxes[..., 0][:, No…...
java通过FTP跨服务器动态监听读取指定目录下文件数据
背景: 1、文件数据在A服务器(windows)(不定期在指定目录下生成),项目应用部署在B服务器(Linux); 2、项目应用在B服务器,监听A服务器指定目录,有新…...
5G边缘计算网关的功能及作用
5G边缘计算网关具有多种功能。 首先,它支持智能云端控制,可以通过5G/4G/WIFI等无线网络将采集的数据直接上云,实现异地远程监测控制、预警通知、报告推送和设备连接等工作。 其次,5G边缘计算网关可以采集各种数据,包…...
阿里云AIGC小说生成【必得京东卡】
任务步骤 此文真实可靠不做虚假宣传,绝对真实,可截图为证。 领取任务 链接(复制到wx打开):#小程序://ITKOL/1jw4TX4ZEhykWJd 教程实践 打开函数计算控制台 应用->创建应用->人工智能->通义千问 AI 助手-…...
数据结构之AVL树
map/multimap/set/multiset这几个容器有个共同点是: 其底层都是按照二叉搜索树来实现的,但是普通的二叉搜索树有其自身的缺陷, 假如往树中插入的元素有序或者接近有序, 二叉搜索树就会退化成单支树, 时间复杂度会退化成O(N),因此map、set等关联式容器的底层结构是对二叉树进行了…...
如何用Java实现一个基于机器学习的情感分析系统,用于分析文本中的情感倾向
背景:练习两年半(其实是两周半),利用工作闲余时间入门一下机器学习,本文没有完整的可实施的案例,由于知识体系不全面,目前代码只能运行,不能准确的预测 卡点: 1 由于过…...
开发聚合支付的的意义
开发聚合支付的意义在于整合各种支付方式,为消费者和商家提供便捷高效的支付体验,同时满足商家的多元化支付需求,提高支付效率和用户体验。 具体来说,聚合支付具有以下意义: 方便快捷:聚合支付整合了多种…...
ChatGPT生产力|中科院学术ChatGPT优化配置
资源链接:GitHub - binary-husky/gpt_academic b站配置讲解链接:chatgpt-academic 新手运行官方精简指南(科研chatgpt拓展) 某知配置图文讲解:图文详解:在windows中部署ChatGPT学术版 - 知乎 (zhihu.com) 一…...
语音播报speechSynthesis最简单的例子(亲测有用)
最简单的例子,在chrome上亲测有效: const utterThis new SpeechSynthesisUtterance(我来试试呀); const synth window.speechSynthesis; synth.speak(utterThis);加入配置,可以配置语言、音量、语速、音高,继续玩: …...
呆头鹅-全自动视频混剪,批量剪辑批量剪视频,探店带货系统,精细化顺序混剪,故事影视解说,视频处理大全,精细化顺序混剪,多场景裂变,多视频混剪
视频闪闪-全自动视频混剪,探店带货系统,多视频混剪,让你成为视频处理大师! 一、全自动视频混剪 www.shipinshanshan.com 你是否曾经厌烦于冗长的视频剪辑过程?是否曾经为了一个短短的混剪视频而熬夜加班?现…...
牛客竞赛网(爱吃素)
题目描述 牛妹是一个爱吃素的小女孩,所以很多素数都害怕被她吃掉。 一天,两个数字aaa和bbb为了防止被吃掉,决定和彼此相乘在一起,这样被吃掉的风险就会大大降低,但仍有一定的可能被吃掉,请你判断他们相乘后…...
基于高效多分支卷积神经网络的生长点精确检测与生态友好型除草
Eco-friendly weeding through precise detection ofgrowing points via efficient multi-branch convolutional neural networks 摘要1、介绍2、相关工作2.1 杂草检测,高效除草2.2 用于密集预测任务的编解码网络2.3 语义图形是一种有效的标签方法3、总结摘要 在本研究中,我…...
11月9日,每日信息差
今天是2023年11月09日,以下是为您准备的17条信息差 第一、中国电信在进博会上与诺基亚、爱立信、英特尔、戴尔、三星达成采购合作意向。采购范围涵盖无线、数据和传输、固网终端、服务器、CPU、手机终端等设备及服务 第二、马斯克称SpaceX明年将每两天发射一次火箭…...
什么是 eCPM?它与 CPM 有何不同?
目录 eCPM 什么是 eCPM?它与 CPM 有何不同? 如何计算 eCPM? 该指标的主要优势有哪些? eCPM 底价 eCPM 达到多少比较合适? eCPM 每千人有效成本 (eCPM) 是指发行商(App 开发者)在 App 中每…...
Power Automate-创建和运行
网站:Microsoft Power Automate 根据自己需求选择创建 选择需要的触发方式,以即时云端流为例,点击触发流 点击添加新步骤 可以选择多种微软应用或者自定义应用连接 此处以向SharePoint列表追加项为例,要提前创建好SharePoint列表…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
ubuntu22.04有线网络无法连接,图标也没了
今天突然无法有线网络无法连接任何设备,并且图标都没了 错误案例 往上一顿搜索,试了很多博客都不行,比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动,重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...
Unity VR/MR开发-VR开发与传统3D开发的差异
视频讲解链接:【XR马斯维】VR/MR开发与传统3D开发的差异【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...

