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 + nnums2.length == n0 <= m, n <= 2001 <= 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) 按使用场景和性质分类 公网(全球网络) 外网 内网(私有网…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
