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

Leetcode 合并两个数组

在这里插入图片描述
算法思想是双指针从后往前合并,利用了 nums1 数组的尾部空间来存储合并后的结果,从而避免了额外空间的使用。具体步骤如下:

  1. 初始化指针

    • i 指向 nums1 的有效元素末尾,即位置 m - 1
    • j 指向 nums2 的末尾,即位置 n - 1
    • k 指向 nums1 的最后一个位置,即 m + n - 1,这是合并后数组的尾部位置。
  2. 从尾部开始比较和填充

    • 使用 while 循环从后往前遍历,比较 nums1[i]nums2[j] 的大小。
    • 如果 nums1[i] 大于 nums2[j],将 nums1[i] 的值赋给 nums1[k],然后将指针 ik 分别左移(递减)。
    • 如果 nums2[j] 大于等于 nums1[i],则将 nums2[j] 的值赋给 nums1[k],然后将指针 jk 左移。
    • 这个过程不断将较大的元素放到 nums1 的后部,从而保证结果是非递减排序的。
  3. 处理剩余的 nums2 元素

    • nums1 的元素已经全部比较完后(即 i < 0),如果 nums2 中还有剩余元素(即 j >= 0),则将 nums2 中剩下的所有元素直接复制到 nums1 的开头部分。因为 nums2 本身是有序的,所以直接复制即可。
  4. 时间复杂度和空间复杂度

    • 该算法的时间复杂度为 (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 的元素。

具体原因如下:

  1. 预留空间的设计:题目要求将 nums2 的元素合并到 nums1 中。nums1 的数组长度是 m + n,其中前 m 个位置是 nums1 的有效元素,后 n 个位置是用来放 nums2 的元素的空间(这些位置最初被填充为 0)。因此,从逻辑上讲,nums1 的所有有效元素在一开始就已经包含在数组的前 m 个位置上。

  2. 从后向前合并的策略:代码中使用了从后向前合并的策略,即从 nums1nums2 的末尾元素开始逐个比较,将较大的元素放到 nums1 的最后位置(k = m + n - 1),依次向前填充。因此,在合并过程中,nums1 的所有有效元素要么已经被比较并放置在正确的位置,要么在 while 循环结束时已经全部处理完。

  3. 可能剩余的情况:如果 nums2 的元素较小(即 nums2 中的元素比 nums1 中的剩余元素更小),则 nums2 中可能会有未处理的元素。这是因为 while 循环中的条件是 i >= 0 && j >= 0,一旦 i < 0(即 nums1 的有效元素已经处理完),while 循环结束,接下来只需要将 nums2 中剩下的元素(如果有)放到 nums1 的前部位置即可。

  4. 剩余的处理方式:当 nums1 的有效元素都已处理完(即 i < 0),但 nums2 中还有未处理的元素(j >= 0),这些剩余的 nums2 元素是按非递减顺序排列的,因此可以直接复制到 nums1 的开头。

综上所述,在第一个 while 循环结束后,nums1 中的有效元素(前 m 个)要么已经放置到正确位置,要么已经被用来比较且完全填充到数组后部,而 nums2 中的元素如果还未处理完,则直接复制到 nums1 开头。这就是为什么第一个 while 循环结束后只可能有 nums2 中的元素剩余。

相关文章:

Leetcode 合并两个数组

算法思想是双指针从后往前合并&#xff0c;利用了 nums1 数组的尾部空间来存储合并后的结果&#xff0c;从而避免了额外空间的使用。具体步骤如下&#xff1a; 初始化指针&#xff1a; i 指向 nums1 的有效元素末尾&#xff0c;即位置 m - 1。j 指向 nums2 的末尾&#xff0c;即…...

Native Crash 信号速查

重点信号 SIGSEGV&#xff08;11&#xff09; signal segmentation violation&#xff1a;段错误无效内存访问访问无权访问的内存空指针、越界访问&#xff08;mmap&#xff1f;&#xff09; SIGBUS&#xff08;7&#xff09; Bus Error&#xff1a;总线错误非法内存访问访问 …...

【工具变量】自由贸易试验区试点DID数据集(2003-2023年)

数据简介&#xff1a;自由贸易试验区&#xff08;Free Trade Zone&#xff0c;简称FTZ&#xff09;是中国ZF在新形势下为了推进GG开放、提高开放型经济水平而采取的重要战略举措。自贸试验区在一国的部分领土内运入任何货物&#xff0c;被认为在关境以外&#xff0c;免于实施惯…...

js-在数组中根据name查找出对应id(find与filter方法)

1.根据name查找出对应id 使用数组的 find 方法来根据对象的某个属性&#xff08;如名称&#xff09;查找对应的对象&#xff0c;并获取该对象的 id 属性。 2.find 方法 const array [ { id: 1, name: Alice }, { id: 2, name: Bob }, { id: 3, name: Charlie } ]; 使用…...

推荐:自然语言处理方向的一些创新点

以下是自然语言处理研究方向的一些创新点&#xff1a; 一、预训练模型的改进与优化 模型架构创新 融合多模态信息&#xff1a; 传统的自然语言处理模型主要处理文本信息。创新点在于将图像、音频等多模态信息融合到预训练模型中。例如&#xff0c;对于描述一幅画的文本&#x…...

成都睿明智科技有限公司抖音电商服务的领航者

在这个短视频风起云涌的时代&#xff0c;抖音电商以其独特的魅力迅速崛起&#xff0c;成为无数商家争夺流量与销量的新战场。在这片红海之中&#xff0c;如何脱颖而出&#xff0c;实现销售额的飞跃&#xff1f;今天&#xff0c;就让我们一同走进成都睿明智科技有限公司&#xf…...

【大数据学习 | kafka】kafka的整体框架与数据结构

1. kafka的整体框架 首先kafka启动以后所有的broker都会向zookeeper进行注册&#xff0c;在/brokers/ids中以列表的形式展示所有的节点&#xff0c;在/controller节点中使用独享锁实现broker的选举&#xff0c;其中一个机器为主节点。其他的为从节点&#xff0c;选举的根本原则…...

隐私保护下的数据提取策略

在隐私保护下进行数据提取&#xff0c;需要采取一系列策略来确保个人隐私得到妥善保护&#xff0c;同时满足数据使用的需求。以下是一些关键的策略和方法&#xff1a; 一、数据最小化原则 定义&#xff1a;仅收集和提取必要的数据&#xff0c;避免收集过多的个人信息或不相关…...

vue 和 django 报 CORS(跨域资源共享,Cross-Origin Resource Sharing)是一种跨域访问的机制,

在使用 Vue 和 Django 进行前后端分离开发时&#xff0c;如果遇到 AxiosError: Network Error 的错误&#xff0c;通常可能是由于以下几种原因引起的。下面列出了一些常见的原因和解决方案。 1. CORS&#xff08;跨源资源共享&#xff09;问题 当你的 Vue 应用和 Django 后端…...

「Mac畅玩鸿蒙与硬件3」鸿蒙开发环境配置篇3 - DevEco Studio 插件安装与配置

本篇将专注于如何在 DevEco Studio 中安装和配置必要的插件&#xff0c;以增强开发功能和提升效率。通过正确配置插件&#xff0c;开发流程能够得到简化&#xff0c;开发体验也会更加顺畅。 关键词 插件安装配置优化DevEco Studio开发工具 一、插件的重要性 插件可以大幅扩展…...

【论文阅读】PGAN

1. WHY 问题 图像超分辨率一直是一个热门研究课题&#xff0c;具有重要的应用价值。基于生成对抗网络GAN的单幅图像超分辨率方法显示重建图像与人类视觉特征更一致。因此&#xff0c;基于 GAN 的网络优化已成为图像超分辨率的主流。然而&#xff0c;一些最新研究表明&#xf…...

基于Unet卷积神经网络的脑肿瘤MRI分割

项目源码获取方式见文章末尾&#xff01; 回复暗号&#xff1a;13&#xff0c;免费获取600多个深度学习项目资料&#xff0c;快来加入社群一起学习吧。 《------往期经典推荐------》 项目名称 1.【YOLO模型实现农作物病虫害虫识别带GUI界面】 2.【卫星图像道路检测DeepLabV3P…...

[java][基础]HTTPTomcatServlet

1&#xff0c;Web概述 1.1 Web和JavaWeb的概念 Web是全球广域网&#xff0c;也称为万维网(www)&#xff0c;能够通过浏览器访问的网站。 在我们日常的生活中&#xff0c;经常会使用浏览器去访问百度、京东、传智官网等这些网站&#xff0c;这些网站统称为Web网站。如下就是通…...

【开源免费】基于SpringBoot+Vue.JS网上超市系统(JAVA毕业设计)

本文项目编号 T 037 &#xff0c;文末自助获取源码 \color{red}{T037&#xff0c;文末自助获取源码} T037&#xff0c;文末自助获取源码 目录 一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析 六、核心代码6.1 查…...

【单片机】深入剖析USART与UART的区别

在嵌入式系统和微控制器开发中&#xff0c;串行通信是一个非常关键的概念&#xff0c;涉及到不同设备之间的数据传输。常见的串行通信协议包括UART&#xff08;Universal Asynchronous Receiver/Transmitter&#xff09;和USART&#xff08;Universal Synchronous/Asynchronous…...

‌Linux tac命令‌

‌Linux tac命令‌是一个用于逆序显示文件内容的工具&#xff0c;其名称来源于“cat”的反向拼写。tac命令的基本功能是将文件的内容从最后一行开始输出&#xff0c;直到第一行结束&#xff0c;这与cat命令的功能相反&#xff0c;cat命令是从第一行开始输出直到最后一行。 tac…...

从简单的demo开始让您逐步了解GetX的用法

目录 前言 一、从demo开始体现下Getx的用法 二、从最简单的功能开始 1.新建一个Flutter工程 2.GetX初体验 1.路由跳转 1.普通路由跳转 2.跳转并从堆栈中销毁当前页面 3.跳转并销毁之前所有页面 4.跳转以及传值 2.更方便的实现SnackBar、Dialog、BottomSheet 三、Ge…...

JAVA的动态代理

Java 动态代理是 Java 语言中一项强大的特性&#xff0c;它允许在运行时动态地创建符合一组接口的代理类。这种机制广泛应用于各种框架和工具中&#xff0c;如 Spring AOP、Hibernate 数据查询、Mockito 测试框架等。通过动态代理&#xff0c;可以在不修改原有代码的前提下&…...

「图文详解」Pycharm 远程服务器Debug

首先声明一点&#xff0c;社区版的无法使用&#xff0c;需要使用 专业版Pycharm 才可以使用&#xff0c;至于密钥可以去TB购入&#xff0c;价格低廉、有效期长 相信很多小伙伴会面临本地电脑显存不够&#xff0c;但是服务器代码又无法直观的调试&#xff0c;只能靠打日志的方法…...

Golang反射在实际开发中的应用场景

Golang反射在实际开发中的应用场景 当然可以&#xff0c;以下是一些使用Go语言反射的实际开发场景&#xff1a; 1. 通用处理函数 当你需要编写一个函数&#xff0c;它可以处理不同类型的参数时&#xff0c;反射可以让你在运行时检查和操作这些参数。 示例代码&#xff1a; …...

web vue 项目 Docker化部署

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

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...