浙江省建设工程质量安全管理协会网站/网页优化方法
目录
- 题目
- 引用
- 描述
- 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--;}}
}
以下是代码的逻辑和特点:
-
初始化指针:
p1
和p2
分别初始化为m - 1
和n - 1
,指向nums1
和nums2
的最后一个元素。
-
初始化尾部指针:
tail
初始化为m + n - 1
,指向nums1
数组的末尾位置,这是合并后数组的最后一个元素的位置。
-
循环逻辑:
- 循环继续进行,直到
p1
和p2
至少有一个到达数组的开始位置(即p1 >= 0
或p2 >= 0
)。
- 循环继续进行,直到
-
选择元素:
- 如果
p1
已经到达数组的开始位置(即-1
),则选择nums2
中的元素。 - 如果
p2
已经到达数组的开始位置,选择nums1
中的元素。 - 如果两个指针都在数组范围内,比较
nums1[p1]
和nums2[p2]
的值,选择较小的元素。
- 如果
-
填充尾部:
- 将选择的元素
cur
放入nums1[tail]
,然后更新tail
的位置。
- 将选择的元素
-
指针更新:
- 根据选择的元素来自哪个数组,相应地更新
p1
或p2
的值。
- 根据选择的元素来自哪个数组,相应地更新
-
循环结束:
- 当
p1
和p2
都到达数组的开始位置时,循环结束,此时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.后逆向双指针进阶:你可以设计实现一个时间复杂度为 O(m n) 的算法解决此问题吗?总结 题目 来自力扣 引用 合并两个有序数组 给你两个按 **非递减顺序 **排列的整数数组 nums1 和 nums2,另有两个整…...

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

FastAPI(七十五)实战开发《在线课程学习系统》接口开发-- 创建课程
源码见:"fastapi_study_road-learning_system_online_courses: fastapi框架实战之--在线课程学习系统" 上次我们分享了,FastAPI(七十四)实战开发《在线课程学习系统》接口开发-- 删除留言 从本篇文章开始,…...

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

linux下载redis安装并指定配置文件启动
linux下载redis并安装启动: 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 修改…...

线性结构、线性表、顺序表、链表、头插法、尾插法、中间插入或删除一个节点
梳理几个名词: 逻辑地址:就是说是第几个元素。 物理地址:也就是存储地址,在计算机里具体存放的位置。 线性表的存储结构分为: (1)顺序存储结构:将数据依次存储在连续的整块物理空…...

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# 中用于并行编程的一个的方法,它属于 System.Threa…...

vue2 前端实现pdf在线预览(无插件版)
toFielDetail()是点击预览的方法,getOfficialFile是获取文件流的接口正常定义即可: export function getOfficialFile(query) {return request({url: /dataAsset/projectassess/getOfficialFile,method: get,params: query,}); } 调用接口的页面需要引用…...

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

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

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

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

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

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

吴恩达机器学习C1W2Lab06-使用Scikit-Learn进行线性回归
前言 有一个开源的、商业上可用的机器学习工具包,叫做scikit-learn。这个工具包包含了你将在本课程中使用的许多算法的实现。 目标 在本实验室你可以: 利用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% }}>状态&…...

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

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

STM32_RTOS学习笔记——1(列表与列表项)
总体RTOS笔记目录 一,列表与列表项(本文) 二,待定 视频参考:B站野火 一,C语言列表概念 列表就是C语言中的链表,链表就如同下面的衣架一样,需要的各种内容可以参考 C语言链表可…...

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

javaweb_02:Maven
一、引入 在javaweb的开发中,需要使用大量的jar包,我们得手动去导入,而Maven可以自动帮我们导入和配置这个jar包。 二、Maven项目框架管理工具 核心思想:约定大于配置(有约束不违反):Maven会…...

19.延迟队列优化
问题 前面所讲的延迟队列有一个不足之处,比如现在有一个需求需要延迟半个小时的消息,那么就只有添加一个新的队列。那就意味着,每新增一个不同时间需求,就会新创建一个队列。 解决方案 应该讲消息的时间不要跟队列绑定…...

P10477 Subway tree systems 题解,c++ 树相关题目
题目 poj 链接 洛谷链接 n n n 组数据,每组数据给定两个 01 01 01 串(长度不超过 3000 3000 3000),意思如下: 对于每一个 0 0 0,代表该节点有一个子节点,并前往该子节点。对于每一个 1 1 …...

18.jdk源码阅读之CopyOnWriteArrayList
1. 写在前面 CopyOnWriteArrayList 是 Java 中的一种线程安全的 List 实现,基于“写时复制”(Copy-On-Write)机制。下面几个问题大家可以先思考下,在阅读源码的过程中都会解答: CopyOnWriteArrayList 适用于哪些场景…...

美股:AMD展现乐观前景,挑战AI加速器市场霸主
在科技行业的激烈竞争中,AMD公司近期发布了对当前季度收入的乐观预测,显示出其新推出 一、AMD第三季度营收预期超越分析师平均预期 AMD在周二的声明中预计,第三季度营收将达到约67亿美元,这一数字超出了分析师此前平均预期的66.…...

如何提高计算机视觉技术在复杂环境和低光照条件下的物体识别准确率?
要在复杂环境和低光照条件下提高计算机视觉技术的物体识别准确率,可以采取以下几个方法: 数据增强:在训练集中添加各种复杂环境和低光照条件下的图片,通过增加数据的多样性,使算法能够更好地适应各种场景。 预处理&am…...

ubuntu cmake使用自己版本的qt
给一篇文章参考 https://blog.csdn.net/bank_dreamer/article/details/138678909 自己使用的范例 set(Qt5_DIR "/home/peak/Qt5.14.0/5.14.0/gcc_64/lib/cmake/Qt5")# 设置Qt5的安装目录 #set(CMAKE_PREFIX_PATH "/home/peak/Qt5.14.0")find_package(Qt5…...

Python基础知识笔记---保留字
保留字,也称关键字,是指被编程语言内部定义并保留使用的标识符。 一、保留字概览 二、保留字用途 1. False:表示布尔值假。 2. None:表示空值或无值。 3. True:表示布尔值真。 4. not:布尔逻辑操作符…...

Python面试整理-Web开发
在Python中,Web开发可以利用多种强大的框架和库来构建从简单的静态网页到复杂的动态Web应用。以下是几种流行的Python Web开发框架和相关技术的概述: 1. Flask Flask 是一个轻量级的Web应用框架,它非常灵活,适用于小型到中型项目,或作为构建微服务的基础。Flask的核心非常…...

民大食堂用餐小程序的设计
管理员账户功能包括:系统首页,个人中心,用户管理,商家管理,档口号管理,商家餐品管理,餐品种类管理,购物车管理,订单信息管理 微信端账号功能包括:系统首页&a…...