Leetcode 面试150题 88.合并两个有序数组 简单
系列博客目录
文章目录
- 系列博客目录
- 88. 合并两个有序数组 简单
- 示例 1:
- 示例 2:
- 示例 3:
- 提示:
- 问题:
88. 合并两个有序数组 简单
给你两个按 非递减顺序 排列的整数数组 nums1
和 nums2
,另有两个整数 m
和 n
,分别表示 nums1
和 nums2
中的元素数目。
请你 合并 nums2
到 nums1
中,使合并后的数组同样按 非递减顺序 排列。
注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1
中。 为了应对这种情况,nums1
的初始长度为 m + n
,其中前 m
个元素表示应合并的元素,后 n
个元素为 0,默认忽略。
示例 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]
解释:
由于 m = 0,所以 nums1 中没有元素。
需要合并的数组仅为 nums2 。
结果是 [1],nums1 中的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10^9 <= nums1[i], nums2[j] <= 10^9
问题:
你可以设计一个时间复杂度为 O(m + n)
的算法解决此问题吗?
我的思路是先判断特殊情况,然后先把nums1中的小于nums2[0]
的放入最后结果数组result中,再用双指针。
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int[] result = new int[nums1.length+1];Arrays.fill(result, 0);int index = 0;int index_nums2 = 0;int index_nums1 = 0;if(n == 0){return;}if(m==0){for (int i = 0; i < nums2.length; i++) {nums1[i]=nums2[i];}return;}//下面这个while循环之后发现没必要while(nums1[index_nums1]<nums2[index_nums2]){result[index]=nums1[index_nums1];if(index_nums1==m){for(int l =index_nums2;l<nums2.length;l++){result[index++]=nums2[index_nums2++];}for (int i = 0; i < nums1.length; i++) {nums1[i]=result[i];}return;}index_nums1++;index++;}while(index_nums1<m||index_nums2<n){while(nums1[index_nums1]<=nums2[index_nums2]){result[index++]=nums1[index_nums1++];if(index_nums1==m){for(int l =index_nums2;l<n;l++){result[index++]=nums2[index_nums2++];}for (int i = 0; i < nums1.length; i++) {nums1[i]=result[i];}return;}}while(nums2[index_nums2]<=nums1[index_nums1]){result[index++]=nums2[index_nums2++];if(index_nums2==n){for(int l =index_nums1;l<m;l++){result[index++]=nums1[index_nums1++];}for (int i = 0; i < nums1.length; i++) {nums1[i]=result[i];}return;}}}}
}
后来发现其中,一段代码没有必要,也就是不用先把nums1中的小于nums2[0]
的放入最后结果数组result中,再用双指针,可以直接使用双指针。
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int[] result = new int[nums1.length+1];Arrays.fill(result, 0);int index = 0;int index_nums2 = 0;int index_nums1 = 0;if(n == 0){return;}if(m==0){for (int i = 0; i < nums2.length; i++) {nums1[i]=nums2[i];}return;}while(index_nums1<m||index_nums2<n){while(nums1[index_nums1]<=nums2[index_nums2]){result[index++]=nums1[index_nums1++];if(index_nums1==m){//判断特殊,即nums1数组已经处理完毕,只省下nums2数组for(int l =index_nums2;l<n;l++){result[index++]=nums2[index_nums2++];}for (int i = 0; i < nums1.length; i++) {//整理结果nums1[i]=result[i];}return;}}while(nums2[index_nums2]<=nums1[index_nums1]){result[index++]=nums2[index_nums2++];if(index_nums2==n){for(int l =index_nums1;l<m;l++){result[index++]=nums1[index_nums1++];}for (int i = 0; i < nums1.length; i++) {//整理结果nums1[i]=result[i];}return;}}}}
}
官网的双指针,自己的麻烦地方在于没有想到用一个while循环即可实现,自己想的是,判断完了该取哪个数组的值后,在数组中用while连续取值,但是应该是一个while,在这个while里面觉得从哪个数组取值,自己的思路和官方的思路,顺序相反。
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 = 0, p2 = 0;int[] sorted = new int[m + n];int cur;while (p1 < m || p2 < n) {if (p1 == m) {cur = nums2[p2++];} else if (p2 == n) {cur = nums1[p1++];} else if (nums1[p1] < nums2[p2]) {cur = nums1[p1++];} else {cur = nums2[p2++];}sorted[p1 + p2 - 1] = cur;}for (int i = 0; i != m + n; ++i) {nums1[i] = sorted[i];}}
}作者:力扣官方题解
链接:https://leetcode.cn/problems/merge-sorted-array/solutions/666608/he-bing-liang-ge-you-xu-shu-zu-by-leetco-rrb0/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
复杂度分析
-
时间复杂度: (O(m + n))。
指针移动单调递增,最多移动 (m + n) 次,因此时间复杂度为 (O(m + n))。 -
空间复杂度: (O(m + n))。
需要建立长度为 (m + n) 的中间数组sorted
。
相关文章:
Leetcode 面试150题 88.合并两个有序数组 简单
系列博客目录 文章目录 系列博客目录88. 合并两个有序数组 简单示例 1:示例 2:示例 3:提示:问题: 88. 合并两个有序数组 简单 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n,分别表示 nums1 和 nums2 中的元素数目。 请你…...

CGAL CGAL::Polygon_mesh_processing::self_intersections解析
CGAL::Polygon_mesh_processing::self_intersections 是用于检测多边形网格(Polygon Mesh)中的自相交的函数。自相交是指网格中的某些面(例如三角形)与同一网格中的其他面交叉的情况。这种情况通常是不期望的,因为它会…...
esp32触发相机
esp32触发相机,测试成功上升沿触发 串口发送命令 up 20000 1 20000 触发 #include <Arduino.h>const int outputPin 12; // 输出引脚 String inputCommand ""; // 串口输入缓冲区// 解析命令参数,例如 "up 10 5" 解析为…...
webrtc支持h265
Webrtc播放H265的技术探索(datachannelwasm) - 飞翔天空energy - 博客园 https://github.com/ZLMediaKit/ZLMediaKit/issues/3589 [技术咨询]addStreamProxy 添加拉流代理之后,webrtc协议无法播放,其它协议正常 Issue #1808 ZLMediaKit/ZLMediaKit G…...

macos 14.0 Monoma 修改顶部菜单栏颜色
macos 14.0 设置暗色后顶部菜单栏还维持浅色,与整体不协调。 修改方式如下:...

在 Mac(ARM 架构)上安装 JDK 8 环境
文章目录 步骤 1:检查系统版本步骤 2:下载支持 ARM 的 JDK 8步骤 3:安装 JDK步骤 4:配置环境变量步骤 5:验证安装步骤 6:注意事项步骤7:查看Java的安装路径 在 Mac(ARM 架构…...

Linux高阶——1123—
1、服务器版本介绍及实现 1、单进程单任务服务器(阻塞IO) 单进程模型,阻塞IO冲突,等待连接时无法读取数据,读取数据时无法连接 比较适合处理单任务,排队处理业务 伪代码 while(true) {addrlensizeof(c…...

VOLO实战:使用VOLO实现图像分类任务(二)
文章目录 训练部分导入项目使用的库设置随机因子设置全局参数图像预处理与增强读取数据设置Loss设置模型设置优化器和学习率调整策略设置混合精度,DP多卡,EMA定义训练和验证函数训练函数验证函数调用训练和验证方法 运行以及结果查看测试完整的代码 在上…...

【kafka02】消息队列与微服务之Kafka部署
Kafka 部署 Kafka 部署说明 kafka 版本选择 kafka 基于scala语言实现,所以使用kafka需要指定scala的相应的版本.kafka 为多个版本的Scala构建。这仅在使用 Scala 时才重要,并且希望为使用的相同 Scala 版本构建一个版本。否则,任何版本都可以 kafka下…...

MySQL系列之数据类型(Numeric)
导览 前言一、数值类型综述二、数值类型详解1. NUMERIC1.1 UNSIGNED或SIGNED1.2 数据类型划分 2. Integer类型取值和存储要求3. Fixed-Point类型取值和存储要求4. Floating-Point类型取值和存储要求 结语精彩回放 前言 MySQL系列最近三篇均关注了和我们日常工作或学习密切相关…...

BERT简单理解;双向编码器优势
目录 BERT简单理解 一、BERT模型简单理解 二、BERT模型使用举例 三、BERT模型的优势 双向编码器优势 BERT简单理解 (Bidirectional Encoder Representations from Transformers)模型是一种预训练的自然语言处理(NLP)模型,由Google于2018年推出。以下是对BERT模型的简…...

LLamafactory 批量推理与异步 API 调用效率对比实测
背景 在阅读 LLamafactory 的文档时候,发现它支持批量推理: 推理.https://llamafactory.readthedocs.io/zh-cn/latest/getting_started/inference.html 。 于是便想测试一下,它的批量推理速度有多快。本文实现了 下述两种的大模型推理,并对…...

spf算法、三类LSA、区间防环路机制/规则、虚连接
1.构建spf树: 路由器将自己作为最短路经树的树根根据Router-LSA和Network-LSA中的拓扑信息,依次将Cost值最小的路由器添加到SPF树中。路由器以Router ID或者DR标识。广播网络中DR和其所连接路由器的Cost值为0。SPF树中只有单向的最短路径,保证了OSPF区域内路由计管不…...

C语言学习 12(指针学习1)
一.内存和地址 1.内存 在讲内存和地址之前,我们想有个⽣活中的案例: 假设有⼀栋宿舍楼,把你放在楼⾥,楼上有100个房间,但是房间没有编号,你的⼀个朋友来找你玩,如果想找到你,就得挨…...
TypeError: issubclass() arg 1 must be a class
TypeError: issubclass() arg 1 must be a class 报错代码: import spacy 原因: 库版本错误, 解决方法: pip install typing-inspect0.8.0 typing_extensions4.5.0 感谢作者: langchain TypeError: issubclass() …...
Java面试题、八股文学习之JVM篇
1.对象一定分配在堆中吗?有没有了解逃逸分析技术? 对象不一定总是分配在堆中。在Java等一些高级编程语言中,对象的分配位置可以通过编译器或运行时系统的优化来决定。其中,逃逸分析(Escape Analysis)是用于…...

【eNSP】动态路由协议RIP和OSPF
动态路由RIP(Routing Information Protocol,路由信息协议)和OSPF(Open Shortest Path First,开放式最短路径优先)是两种常见的动态路由协议,它们各自具有不同的特点和使用场景。本篇会对这两种协…...

春秋云境 CVE 复现
CVE-2022-4230 靶标介绍 WP Statistics WordPress 插件13.2.9之前的版本不会转义参数,这可能允许经过身份验证的用户执行 SQL 注入攻击。默认情况下,具有管理选项功能 (admin) 的用户可以使用受影响的功能,但是该插件有一个设置允许低权限用…...

Linux入门攻坚——39、Nginx入门
Nginx:engine X Tengine:淘宝改进维护的版本 Registry: 使用了libevent库:高性能的网络库 epoll()函数 Nginx特性: 模块化设计、较好的扩展性;(但不支持动态加载模块功能&#…...

计算机网络的类型
目录 按覆盖范围分类 个人区域网(PAN) 局域网(LAN) 城域网(MAN) 4. 广域网(WAN) 按使用场景和性质分类 公网(全球网络) 外网 内网(私有网…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...

Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...

Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践
前言:本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中,跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南,你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案,并结合内网…...

Android写一个捕获全局异常的工具类
项目开发和实际运行过程中难免会遇到异常发生,系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler,它是Thread的子类(就是package java.lang;里线程的Thread)。本文将利用它将设备信息、报错信息以及错误的发生时间都…...