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

Leetcode 面试150题 88.合并两个有序数组 简单

系列博客目录


文章目录

  • 系列博客目录
  • 88. 合并两个有序数组 简单
    • 示例 1:
    • 示例 2:
    • 示例 3:
    • 提示:
    • 问题:


88. 合并两个有序数组 简单

给你两个按 非递减顺序 排列的整数数组 nums1nums2,另有两个整数 mn,分别表示 nums1nums2 中的元素数目。

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

注意:最终,合并后数组不应由函数返回,而是存储在数组 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&#xff0c;另有两个整数 m 和 n&#xff0c;分别表示 nums1 和 nums2 中的元素数目。 请你…...

CGAL CGAL::Polygon_mesh_processing::self_intersections解析

CGAL::Polygon_mesh_processing::self_intersections 是用于检测多边形网格&#xff08;Polygon Mesh&#xff09;中的自相交的函数。自相交是指网格中的某些面&#xff08;例如三角形&#xff09;与同一网格中的其他面交叉的情况。这种情况通常是不期望的&#xff0c;因为它会…...

esp32触发相机

esp32触发相机&#xff0c;测试成功上升沿触发 串口发送命令 up 20000 1 20000 触发 #include <Arduino.h>const int outputPin 12; // 输出引脚 String inputCommand ""; // 串口输入缓冲区// 解析命令参数&#xff0c;例如 "up 10 5" 解析为…...

webrtc支持h265

Webrtc播放H265的技术探索(datachannelwasm) - 飞翔天空energy - 博客园 https://github.com/ZLMediaKit/ZLMediaKit/issues/3589 [技术咨询]addStreamProxy 添加拉流代理之后&#xff0c;webrtc协议无法播放&#xff0c;其它协议正常 Issue #1808 ZLMediaKit/ZLMediaKit G…...

macos 14.0 Monoma 修改顶部菜单栏颜色

macos 14.0 设置暗色后顶部菜单栏还维持浅色&#xff0c;与整体不协调。 修改方式如下&#xff1a;...

在 Mac(ARM 架构)上安装 JDK 8 环境

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

Linux高阶——1123—

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

VOLO实战:使用VOLO实现图像分类任务(二)

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

【kafka02】消息队列与微服务之Kafka部署

Kafka 部署 Kafka 部署说明 kafka 版本选择 kafka 基于scala语言实现,所以使用kafka需要指定scala的相应的版本.kafka 为多个版本的Scala构建。这仅在使用 Scala 时才重要&#xff0c;并且希望为使用的相同 Scala 版本构建一个版本。否则&#xff0c;任何版本都可以 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 的文档时候&#xff0c;发现它支持批量推理: 推理.https://llamafactory.readthedocs.io/zh-cn/latest/getting_started/inference.html 。 于是便想测试一下&#xff0c;它的批量推理速度有多快。本文实现了 下述两种的大模型推理&#xff0c;并对…...

spf算法、三类LSA、区间防环路机制/规则、虚连接

1.构建spf树&#xff1a; 路由器将自己作为最短路经树的树根根据Router-LSA和Network-LSA中的拓扑信息,依次将Cost值最小的路由器添加到SPF树中。路由器以Router ID或者DR标识。广播网络中DR和其所连接路由器的Cost值为0。SPF树中只有单向的最短路径,保证了OSPF区域内路由计管不…...

C语言学习 12(指针学习1)

一.内存和地址 1.内存 在讲内存和地址之前&#xff0c;我们想有个⽣活中的案例&#xff1a; 假设有⼀栋宿舍楼&#xff0c;把你放在楼⾥&#xff0c;楼上有100个房间&#xff0c;但是房间没有编号&#xff0c;你的⼀个朋友来找你玩&#xff0c;如果想找到你&#xff0c;就得挨…...

TypeError: issubclass() arg 1 must be a class

TypeError: issubclass() arg 1 must be a class 报错代码&#xff1a; import spacy 原因&#xff1a; 库版本错误&#xff0c; 解决方法&#xff1a; pip install typing-inspect0.8.0 typing_extensions4.5.0 感谢作者&#xff1a; langchain TypeError: issubclass() …...

Java面试题、八股文学习之JVM篇

1.对象一定分配在堆中吗&#xff1f;有没有了解逃逸分析技术&#xff1f; 对象不一定总是分配在堆中。在Java等一些高级编程语言中&#xff0c;对象的分配位置可以通过编译器或运行时系统的优化来决定。其中&#xff0c;逃逸分析&#xff08;Escape Analysis&#xff09;是用于…...

【eNSP】动态路由协议RIP和OSPF

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

春秋云境 CVE 复现

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

Linux入门攻坚——39、Nginx入门

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

计算机网络的类型

目录 按覆盖范围分类 个人区域网&#xff08;PAN&#xff09; 局域网&#xff08;LAN&#xff09; 城域网&#xff08;MAN&#xff09; 4. 广域网&#xff08;WAN&#xff09; 按使用场景和性质分类 公网&#xff08;全球网络&#xff09; 外网 内网&#xff08;私有网…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...