当前位置: 首页 > 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; …...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...