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

编程技巧:如何优雅地合并两个有序数组?

目录

  • 题目
    • 引用
    • 描述
      • 1.直接合并 排序
      • 2.指针
      • 3.后逆向双指针
      • 进阶:你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗?
      • 总结

题目

来自力扣

引用

合并两个有序数组

给你两个按 **非递减顺序 **排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2
中的元素数目。

请你合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。

注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m
个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。

描述

示例 1:

输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6] 解释:需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6]
,其中斜体加粗标注的为 nums1 中的元素。

示例 2:

输入:nums1 = [1], m = 1, nums2 = [], n = 0 输出:[1] 解释:需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3:

输入:nums1 = [0], m = 0, nums2 = [1], n = 1 输出:[1] 解释:需要合并的数组是 [] 和 [1]
。 合并结果是 [1] 。 注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0
仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示:

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109

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

1.直接合并 排序


class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {for(int i=0; i!=n; i++){nums1[m+i]=nums2[i];}Arrays.sort(nums1);}
}

2.指针

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int i = m - 1; // 指向 nums1 中最后一个元素的指针int j = n - 1; // 指向 nums2 中最后一个元素的指针int k = m + n - 1; // 指向 nums1 的末尾的指针// 从两个数组的末尾开始,比较并合并元素while (j >= 0) {if (i >= 0 && nums1[i] > nums2[j]) {nums1[k] = nums1[i--];} else {nums1[k] = nums2[j--];}k--;}}
}

以下是代码的逻辑和特点:

  1. 初始化指针

    • p1p2 分别初始化为 m - 1n - 1,指向 nums1nums2 的最后一个元素。
  2. 初始化尾部指针

    • tail 初始化为 m + n - 1,指向 nums1 数组的末尾位置,这是合并后数组的最后一个元素的位置。
  3. 循环逻辑

    • 循环继续进行,直到 p1p2 至少有一个到达数组的开始位置(即 p1 >= 0p2 >= 0)。
  4. 选择元素

    • 如果 p1 已经到达数组的开始位置(即 -1),则选择 nums2 中的元素。
    • 如果 p2 已经到达数组的开始位置,选择 nums1 中的元素。
    • 如果两个指针都在数组范围内,比较 nums1[p1]nums2[p2] 的值,选择较小的元素。
  5. 填充尾部

    • 将选择的元素 cur 放入 nums1[tail],然后更新 tail 的位置。
  6. 指针更新

    • 根据选择的元素来自哪个数组,相应地更新 p1p2 的值。
  7. 循环结束

    • p1p2 都到达数组的开始位置时,循环结束,此时 nums1 已经被成功合并。

这段代码正确地实现了合并两个有序数组的功能,并且避免了不必要的排序操作。它使用了双指针技术,从两个数组的末尾开始,逐步向前合并,直到所有元素都被合并到 nums1 中。这种方法的时间复杂度为 O(m+n),空间复杂度为 O(1),因为它只使用了常数级别的额外空间。

3.后逆向双指针

public class Solution {// 此方法将nums2合并到nums1中,使得nums1成为有序数组public void merge(int[] nums1, int m, int[] nums2, int n) {// p1指向nums1的最后一个实际元素,p2指向nums2的最后一个实际元素,tail指向合并后nums1的最后一个位置int p1 = m - 1, p2 = n - 1;int tail = m + n - 1;int cur; // cur用于存储当前比较的元素// 当nums1和nums2中还有元素未被合并时,继续循环while (p1 >= 0 || p2 >= 0) {// 如果nums1已经遍历完,直接将nums2中剩余的元素复制到nums1中if (p1 == -1) {cur = nums2[p2--];} // 如果nums2已经遍历完,直接将nums1中剩余的元素复制到nums1中else if (p2 == -1) {cur = nums1[p1--];} // 如果nums1中的当前元素大于nums2中的当前元素,将其复制到nums1的尾部,并移动p1指针else if (nums1[p1] > nums2[p2]) {cur = nums1[p1--];} // 如果nums2中的当前元素大于等于nums1中的当前元素,将其复制到nums1的尾部,并移动p2指针else {cur = nums2[p2--];}// 将cur复制到nums1的tail位置,并将tail向前移动nums1[tail--] = cur;}}
}

进阶:你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗?


class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {// 创建两个指针分别指向两个数组的开头int p1 = 0, p2 = 0;// 创建一个临时数组来存储合并后的结果int[] temp = new int[m + n];// 创建一个指针指向临时数组的开头int p = 0;// 循环遍历两个数组,直到其中一个数组遍历完毕while (p1 < m && p2 < n) {if (nums1[p1] < nums2[p2]) {temp[p++] = nums1[p1++];} else {temp[p++] = nums2[p2++];}}// 如果 nums1 数组还有剩余元素,将其全部复制到临时数组中while (p1 < m) {temp[p++] = nums1[p1++];}// 如果 nums2 数组还有剩余元素,将其全部复制到临时数组中while (p2 < n) {temp[p++] = nums2[p2++];}// 将临时数组的元素复制回原始数组 nums1System.arraycopy(temp, 0, nums1, 0, m + n);}
}

总结

一天的学习结束啦,晚上可以休息啦。明天见

在这里插入图片描述

相关文章:

编程技巧:如何优雅地合并两个有序数组?

目录 题目引用描述1.直接合并 排序2.指针3.后逆向双指针进阶&#xff1a;你可以设计实现一个时间复杂度为 O(m n) 的算法解决此问题吗&#xff1f;总结 题目 来自力扣 引用 合并两个有序数组 给你两个按 **非递减顺序 **排列的整数数组 nums1 和 nums2&#xff0c;另有两个整…...

Vue组件库移动端预览实现原理

引言 大家如果使用过移动端组件库&#xff08;比如&#xff1a;Vant&#xff09;&#xff0c;会发现在网站右侧有一个手机端的预览效果。 而且这个手机端预览的内容和外面的组件代码演示是同步的&#xff0c;切换组件的时候&#xff0c;移动端预览的内容也会发生相应的变化。 …...

FastAPI(七十五)实战开发《在线课程学习系统》接口开发-- 创建课程

源码见&#xff1a;"fastapi_study_road-learning_system_online_courses: fastapi框架实战之--在线课程学习系统" 上次我们分享了&#xff0c;FastAPI&#xff08;七十四&#xff09;实战开发《在线课程学习系统》接口开发-- 删除留言 从本篇文章开始&#xff0c;…...

【C++】 条件变量实现线程同步示例

在做一些比较大的项目的时候&#xff0c;需要实现线程同步&#xff0c; 这里结合一个小示例&#xff0c;进行线程同步的讲解 问题定义 以下是一个使用 C 多线程和条件变量的示例&#xff0c;展示了线程 A 接收一个 enable 信号并通知线程 B 开始工作。线程 B 在开始工作之前…...

linux下载redis安装并指定配置文件启动

linux下载redis并安装启动&#xff1a; cd /usr/local/src 下载redis压缩包 wget http://download.redis.io/releases/redis-6.2.6.tar.gz 解压 tar -xzf redis-6.2.6.tar.gz 编译和安装redis make make install 安装完成后进入 redis 安装目录 cd /usr/local/bin 修改…...

线性结构、线性表、顺序表、链表、头插法、尾插法、中间插入或删除一个节点

梳理几个名词&#xff1a; 逻辑地址&#xff1a;就是说是第几个元素。 物理地址&#xff1a;也就是存储地址&#xff0c;在计算机里具体存放的位置。 线性表的存储结构分为&#xff1a; &#xff08;1&#xff09;顺序存储结构&#xff1a;将数据依次存储在连续的整块物理空…...

C# Task.WaitAll 的用法

目录 简介 1.WaitAll(Task[], Int32, CancellationToken) 2.WaitAll(Task[]) 3.WaitAll(Task[], Int32) 4.WaitAll(Task[], CancellationToken) 5.WaitAll(Task[], TimeSpan) 结束 简介 Task.WaitAll 是 C# 中用于并行编程的一个的方法&#xff0c;它属于 System.Threa…...

vue2 前端实现pdf在线预览(无插件版)

toFielDetail()是点击预览的方法&#xff0c;getOfficialFile是获取文件流的接口正常定义即可&#xff1a; export function getOfficialFile(query) {return request({url: /dataAsset/projectassess/getOfficialFile,method: get,params: query,}); } 调用接口的页面需要引用…...

排序XXXXXXXXX

信息学奥赛&#xff5c;常见排序算法总结&#xff08;C&#xff0b;&#xff09; - 腾讯云开发者社区-腾讯云 (tencent.com) https://cloud.tencent.com/developer/news/975232 常用序号层级排序 一、序号 序号Sequence Number&#xff0c;有顺序的号码&#xff0c;如数字序号…...

【文件解析漏洞】实战详解!

漏洞描述&#xff1a; 文件解析漏洞是由于中间件错误的将任意格式的文件解析成网页可执行文件&#xff0c;配合文件上传漏洞进行GetShell的漏洞! IIS解析漏洞&#xff1a; IIS6.X&#xff1a; 方式一:目录解析 在网站下建立文件夹的名字为.asp/.asa 的文件夹&#xff0c;其目…...

【杂谈】学会让你节省三秒钟——Dev-c++的缺省源

【杂谈】学会让你节省三秒钟——Dev-c的缺省源 1.前言2.缺省源的介绍3.注意 1.前言 你是否在为每次写程序都要自己手打一遍框架而感到苦恼&#xff1f;为什么大佬的Dev-C一新建文件就会自动出现程序框架&#xff1f;看完这篇文章&#xff0c;让你也能成为大佬&#xff0c;不用再…...

推荐一款前端滑动验证码插件(Vue、uniapp)

uniapp版本&#xff1a;滑块拼图验证码&#xff0c;有后端&#xff0c;简单几步即可实现&#xff0c;小程序、h5都可以用 - DCloud 插件市场 Vue版本及cdn版本可以查阅文档&#xff1a; 行为验证 | Poster 文档 示例代码&#xff1a; <template><view id"app&…...

【Git】git stash

目录 基本概念参数详解listshowsavepushpop|applydropclearbranch 参考文章 Git的stash命令是一个非常实用的功能&#xff0c;它允许开发者临时保存工作目录和暂存区的更改&#xff0c;以便能够切换到其他分支或进行其他操作&#xff0c;而不会丢失当前的修改。以下是git stash…...

不得不安利的程序员开发神器,太赞了!!

作为一名程序员&#xff0c;你是否常常为繁琐的后端服务而感到头疼&#xff1f;是否希望有一种工具可以帮你简化开发流程&#xff0c;让你专注于创意和功能开发&#xff1f;今天&#xff0c;我要向大家隆重推荐一款绝佳的开发神器——MemFire Cloud。它专为懒人开发者准备&…...

吴恩达机器学习C1W2Lab06-使用Scikit-Learn进行线性回归

前言 有一个开源的、商业上可用的机器学习工具包&#xff0c;叫做scikit-learn。这个工具包包含了你将在本课程中使用的许多算法的实现。 目标 在本实验室你可以&#xff1a; 利用scikit-learn实现基于正态方程的近似解线性回归 工具 您将使用scikit-learn中的函数以及ma…...

CSS实现表格无限轮播

<div className{styles.tableTh}><div className{styles.thItem} style{{ width: 40% }}>报警名称</div><div className{styles.thItem} style{{ width: 35% }}>开始时间</div><div className{styles.thItem} style{{ width: 25% }}>状态&…...

编程小白如何从迷茫走出

针对新生们常常感到的迷茫&#xff0c;以下是如何选择适合自己的编程语言、如何制定有效的学习计划以及如何避免常见的学习陷阱的详细建议&#xff1a; 一、如何选择适合自己的编程语言 明确需求和目标&#xff1a;不同的编程语言有不同的特点和适用场景。例如&#xff0c;Py…...

14 B端产品的运营管理

通过运营找到需求并通过交换价值提供供给&#xff0c;再逐步扩大规模、站稳脚跟&#xff0c;辅助产品在商业竞争中获胜。 B端产品运营框架 1. 打通渠道 目的&#xff1a;触达客户。 环节&#xff1a;文案策划、活动策划→广告渠道推广→线下BD。 线下BD&#xff1a;通过见面…...

STM32_RTOS学习笔记——1(列表与列表项)

总体RTOS笔记目录 一&#xff0c;列表与列表项&#xff08;本文&#xff09; 二&#xff0c;待定 视频参考&#xff1a;B站野火 一&#xff0c;C语言列表概念 列表就是C语言中的链表&#xff0c;链表就如同下面的衣架一样&#xff0c;需要的各种内容可以参考 C语言链表可…...

子网划分案例

划分子网是将一个较大的网络划分为多个较小的子网&#xff0c;以提高网络管理和安全性 子网划分可以更有效地利用 IP 地址空间&#xff0c;并且有助于控制网络流量、提高网络性能和安全性。 子网划分的主要步骤如下&#xff1a; 确定需要划分的子网数量以及每个子网所需的主…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...