Leetcode 合并两个数组

算法思想是双指针从后往前合并,利用了 nums1 数组的尾部空间来存储合并后的结果,从而避免了额外空间的使用。具体步骤如下:
-
初始化指针:
i指向nums1的有效元素末尾,即位置m - 1。j指向nums2的末尾,即位置n - 1。k指向nums1的最后一个位置,即m + n - 1,这是合并后数组的尾部位置。
-
从尾部开始比较和填充:
- 使用
while循环从后往前遍历,比较nums1[i]和nums2[j]的大小。 - 如果
nums1[i]大于nums2[j],将nums1[i]的值赋给nums1[k],然后将指针i和k分别左移(递减)。 - 如果
nums2[j]大于等于nums1[i],则将nums2[j]的值赋给nums1[k],然后将指针j和k左移。 - 这个过程不断将较大的元素放到
nums1的后部,从而保证结果是非递减排序的。
- 使用
-
处理剩余的
nums2元素:- 当
nums1的元素已经全部比较完后(即i < 0),如果nums2中还有剩余元素(即j >= 0),则将nums2中剩下的所有元素直接复制到nums1的开头部分。因为nums2本身是有序的,所以直接复制即可。
- 当
-
时间复杂度和空间复杂度:
- 该算法的时间复杂度为 (O(m + n)),因为每个元素只被遍历一次。
- 空间复杂度为 (O(1)),因为在
nums1上原地进行合并操作,没有使用额外空间。
这样设计的好处是利用了 nums1 的后半部分空间,避免了新数组的创建,节省了空间。
java 代码
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int i = m - 1;int j = n - 1;int k = m + n - 1;while(i >= 0 && j >= 0) {if(nums1[i] > nums2[j]) {nums1[k--] = nums1[i--];}else {nums1[k--] = nums2[j--];}}while(j >= 0) {nums1[k--] = nums2[j--];}}
}
为什么在第一个while循环结束后,只由nums2有可能仍然还有剩余元素,而不可能是nums1?
在第一个 while 循环结束后,只有 nums2 有可能仍然有剩余元素,而 nums1 不会有剩余的未处理元素,这是因为 nums1 中前 m 个元素已经在数组 nums1 的末尾进行了预留,并且 nums1 的后半部分已被填充为 0,这些 0 的位置就是为了腾出空间来合并 nums2 的元素。
具体原因如下:
-
预留空间的设计:题目要求将
nums2的元素合并到nums1中。nums1的数组长度是m + n,其中前m个位置是nums1的有效元素,后n个位置是用来放nums2的元素的空间(这些位置最初被填充为0)。因此,从逻辑上讲,nums1的所有有效元素在一开始就已经包含在数组的前m个位置上。 -
从后向前合并的策略:代码中使用了从后向前合并的策略,即从
nums1和nums2的末尾元素开始逐个比较,将较大的元素放到nums1的最后位置(k = m + n - 1),依次向前填充。因此,在合并过程中,nums1的所有有效元素要么已经被比较并放置在正确的位置,要么在while循环结束时已经全部处理完。 -
可能剩余的情况:如果
nums2的元素较小(即nums2中的元素比nums1中的剩余元素更小),则nums2中可能会有未处理的元素。这是因为while循环中的条件是i >= 0 && j >= 0,一旦i < 0(即nums1的有效元素已经处理完),while循环结束,接下来只需要将nums2中剩下的元素(如果有)放到nums1的前部位置即可。 -
剩余的处理方式:当
nums1的有效元素都已处理完(即i < 0),但nums2中还有未处理的元素(j >= 0),这些剩余的nums2元素是按非递减顺序排列的,因此可以直接复制到nums1的开头。
综上所述,在第一个 while 循环结束后,nums1 中的有效元素(前 m 个)要么已经放置到正确位置,要么已经被用来比较且完全填充到数组后部,而 nums2 中的元素如果还未处理完,则直接复制到 nums1 开头。这就是为什么第一个 while 循环结束后只可能有 nums2 中的元素剩余。
相关文章:
Leetcode 合并两个数组
算法思想是双指针从后往前合并,利用了 nums1 数组的尾部空间来存储合并后的结果,从而避免了额外空间的使用。具体步骤如下: 初始化指针: i 指向 nums1 的有效元素末尾,即位置 m - 1。j 指向 nums2 的末尾,即…...
Native Crash 信号速查
重点信号 SIGSEGV(11) signal segmentation violation:段错误无效内存访问访问无权访问的内存空指针、越界访问(mmap?) SIGBUS(7) Bus Error:总线错误非法内存访问访问 …...
【工具变量】自由贸易试验区试点DID数据集(2003-2023年)
数据简介:自由贸易试验区(Free Trade Zone,简称FTZ)是中国ZF在新形势下为了推进GG开放、提高开放型经济水平而采取的重要战略举措。自贸试验区在一国的部分领土内运入任何货物,被认为在关境以外,免于实施惯…...
js-在数组中根据name查找出对应id(find与filter方法)
1.根据name查找出对应id 使用数组的 find 方法来根据对象的某个属性(如名称)查找对应的对象,并获取该对象的 id 属性。 2.find 方法 const array [ { id: 1, name: Alice }, { id: 2, name: Bob }, { id: 3, name: Charlie } ]; 使用…...
推荐:自然语言处理方向的一些创新点
以下是自然语言处理研究方向的一些创新点: 一、预训练模型的改进与优化 模型架构创新 融合多模态信息: 传统的自然语言处理模型主要处理文本信息。创新点在于将图像、音频等多模态信息融合到预训练模型中。例如,对于描述一幅画的文本&#x…...
成都睿明智科技有限公司抖音电商服务的领航者
在这个短视频风起云涌的时代,抖音电商以其独特的魅力迅速崛起,成为无数商家争夺流量与销量的新战场。在这片红海之中,如何脱颖而出,实现销售额的飞跃?今天,就让我们一同走进成都睿明智科技有限公司…...
【大数据学习 | kafka】kafka的整体框架与数据结构
1. kafka的整体框架 首先kafka启动以后所有的broker都会向zookeeper进行注册,在/brokers/ids中以列表的形式展示所有的节点,在/controller节点中使用独享锁实现broker的选举,其中一个机器为主节点。其他的为从节点,选举的根本原则…...
隐私保护下的数据提取策略
在隐私保护下进行数据提取,需要采取一系列策略来确保个人隐私得到妥善保护,同时满足数据使用的需求。以下是一些关键的策略和方法: 一、数据最小化原则 定义:仅收集和提取必要的数据,避免收集过多的个人信息或不相关…...
vue 和 django 报 CORS(跨域资源共享,Cross-Origin Resource Sharing)是一种跨域访问的机制,
在使用 Vue 和 Django 进行前后端分离开发时,如果遇到 AxiosError: Network Error 的错误,通常可能是由于以下几种原因引起的。下面列出了一些常见的原因和解决方案。 1. CORS(跨源资源共享)问题 当你的 Vue 应用和 Django 后端…...
「Mac畅玩鸿蒙与硬件3」鸿蒙开发环境配置篇3 - DevEco Studio 插件安装与配置
本篇将专注于如何在 DevEco Studio 中安装和配置必要的插件,以增强开发功能和提升效率。通过正确配置插件,开发流程能够得到简化,开发体验也会更加顺畅。 关键词 插件安装配置优化DevEco Studio开发工具 一、插件的重要性 插件可以大幅扩展…...
【论文阅读】PGAN
1. WHY 问题 图像超分辨率一直是一个热门研究课题,具有重要的应用价值。基于生成对抗网络GAN的单幅图像超分辨率方法显示重建图像与人类视觉特征更一致。因此,基于 GAN 的网络优化已成为图像超分辨率的主流。然而,一些最新研究表明…...
基于Unet卷积神经网络的脑肿瘤MRI分割
项目源码获取方式见文章末尾! 回复暗号:13,免费获取600多个深度学习项目资料,快来加入社群一起学习吧。 《------往期经典推荐------》 项目名称 1.【YOLO模型实现农作物病虫害虫识别带GUI界面】 2.【卫星图像道路检测DeepLabV3P…...
[java][基础]HTTPTomcatServlet
1,Web概述 1.1 Web和JavaWeb的概念 Web是全球广域网,也称为万维网(www),能够通过浏览器访问的网站。 在我们日常的生活中,经常会使用浏览器去访问百度、京东、传智官网等这些网站,这些网站统称为Web网站。如下就是通…...
【开源免费】基于SpringBoot+Vue.JS网上超市系统(JAVA毕业设计)
本文项目编号 T 037 ,文末自助获取源码 \color{red}{T037,文末自助获取源码} T037,文末自助获取源码 目录 一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析 六、核心代码6.1 查…...
【单片机】深入剖析USART与UART的区别
在嵌入式系统和微控制器开发中,串行通信是一个非常关键的概念,涉及到不同设备之间的数据传输。常见的串行通信协议包括UART(Universal Asynchronous Receiver/Transmitter)和USART(Universal Synchronous/Asynchronous…...
Linux tac命令
Linux tac命令是一个用于逆序显示文件内容的工具,其名称来源于“cat”的反向拼写。tac命令的基本功能是将文件的内容从最后一行开始输出,直到第一行结束,这与cat命令的功能相反,cat命令是从第一行开始输出直到最后一行。 tac…...
从简单的demo开始让您逐步了解GetX的用法
目录 前言 一、从demo开始体现下Getx的用法 二、从最简单的功能开始 1.新建一个Flutter工程 2.GetX初体验 1.路由跳转 1.普通路由跳转 2.跳转并从堆栈中销毁当前页面 3.跳转并销毁之前所有页面 4.跳转以及传值 2.更方便的实现SnackBar、Dialog、BottomSheet 三、Ge…...
JAVA的动态代理
Java 动态代理是 Java 语言中一项强大的特性,它允许在运行时动态地创建符合一组接口的代理类。这种机制广泛应用于各种框架和工具中,如 Spring AOP、Hibernate 数据查询、Mockito 测试框架等。通过动态代理,可以在不修改原有代码的前提下&…...
「图文详解」Pycharm 远程服务器Debug
首先声明一点,社区版的无法使用,需要使用 专业版Pycharm 才可以使用,至于密钥可以去TB购入,价格低廉、有效期长 相信很多小伙伴会面临本地电脑显存不够,但是服务器代码又无法直观的调试,只能靠打日志的方法…...
Golang反射在实际开发中的应用场景
Golang反射在实际开发中的应用场景 当然可以,以下是一些使用Go语言反射的实际开发场景: 1. 通用处理函数 当你需要编写一个函数,它可以处理不同类型的参数时,反射可以让你在运行时检查和操作这些参数。 示例代码: …...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...
如何把工业通信协议转换成http websocket
1.现状 工业通信协议多数工作在边缘设备上,比如:PLC、IOT盒子等。上层业务系统需要根据不同的工业协议做对应开发,当设备上用的是modbus从站时,采集设备数据需要开发modbus主站;当设备上用的是西门子PN协议时…...
