当前位置: 首页 > 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;私有网…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

Maven 概述、安装、配置、仓库、私服详解

目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...