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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/479183.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Ubuntu20.04运行msckf_vio

文章目录 环境配置修改编译项目运行MSCKF_VIO运行 Launch 文件运行 rviz播放 ROSBAG 数据集 运行结果修改mskcf 保存轨迹EVO轨迹评价EVO轨迹评估流程实操先把euroc的真值转换为tum&#xff0c;保存为data.tum正式评估 报错1问题描述 报错2问题描述问题分析问题解决 参考 环境配…

vscode下面python调试报错ImportError: cannot import name ‘Literal‘ from ‘typing‘

1 问题描述 我在vscode下面编写python程序&#xff0c;这个程序是在一个英伟达anoconda环境下的项目。之前能运行能调试&#xff0c;最近发现只能运行ctlf5&#xff0c;但是使用f5进行调试时&#xff0c;报错“File “c:\Users\86137.vscode\extensions\ms-python.debugpy-202…

vim 分割窗口后,把状态栏给隐藏

一、基本环境 主机MacOs Sonoma 14.7主机终端Iterm2虚拟机Parallels Desktop 20 for Mac Pro Edition 版本 20.0.1 (55659)虚拟机-操作系统Ubuntu 22.04 最小安装 二、分割窗口后的截图&#xff0c;红色线条部分就是状态栏 分割后个布局是&#xff1a;顶部1行高度窗口&#x…

flink学习(7)——window

概述 窗口的长度(大小): 决定了要计算最近多长时间的数据 窗口的间隔: 决定了每隔多久计算一次 举例&#xff1a;每隔10min,计算最近24h的热搜词&#xff0c;24小时是长度&#xff0c;每隔10分钟是间隔。 窗口的分类 1、根据window前是否调用keyBy分为键控窗口和非键控窗口…

【8210A-TX2】Ubuntu18.04 + ROS_ Melodic + TM-16多线激光 雷达评测

简介&#xff1a;介绍 TM-16多线激光雷达 在8210A载板&#xff0c;TX2核心模块环境&#xff08;Ubuntu18.04&#xff09;下测试ROS驱动&#xff0c;打开使用RVIZ 查看点云数据&#xff0c;本文的前提条件是你的TX2里已经安装了ROS版本&#xff1a;Melodic。 大家好&#xff0c;…

【排版教程】Word、WPS 分节符(奇数页等) 自动变成 分节符(下一页) 解决办法

毕业设计排版时&#xff0c;一般要求每章节的起始页为奇数页&#xff0c;空白页不显示页眉和页脚。具体做法如下&#xff1a; 1 Word 在一个章节的内容完成后&#xff0c;在【布局】中&#xff0c;点击【分隔符】&#xff0c;然后选择【奇数页】 这样在下一章节开始的时&…

【GAMES101笔记速查——Lecture 20 Color and Perception】

颜色与感知 目录 1 光场&#xff08;Light Field / Lumigraph&#xff09; 1.1 全光函数 1.1.1 改进&#xff1a;引入波长 1.1.2 改进&#xff1a;添加时间t 1.1.3 改进&#xff1a;人可以移动&#xff0c;添加空间坐标 1.1.4 改进&#xff1a;不把函数当电影来看。 1.…

HTML5和CSS3新增特性

HTML5的新特性 HTML5新增的语义化标签 HTML5 的新增特性主要是针对于以前的不足&#xff0c;增加了一些新的标签、新的表单和新的表单属性等。 这些新特性都有兼容性问题&#xff0c;基本是 IE9 以上版本的浏览器才支持&#xff0c;如果不考虑兼容性问题&#xff0c;可以大量…

ArcGIS+deck.gl矢量切片三维化表示建筑白模

01 背景介绍 很多ArcGIS API for JavaScript的用户想要ArcGIS的矢量切片技术体系实现Mapbox gl将城市建筑物footprint矢量切片三维化成建筑白模的效果。效果如图&#xff1a;截图来自mapbox studio1但目前仅靠ArcGIS VectorTileServer 和 ArcGIS API for JavaScript本身无法达…

Windows下安装FreeSurfer教程

简介 FreeSurfer 是一个开源软件包&#xff0c;用于分析和可视化横断面和纵向研究的结构、功能和扩散神经成像数据。它由Athinoula A. Martinos 生物医学成像中心的计算神经成像实验室开发。 官网 功能 FreeSurfer 为结构 MRI 数据提供完整的处理流&#xff0c;包括&#xf…

RTMP协议

背景介绍 RTMP&#xff08;Real Time Messaging Protocol&#xff09; 是由 Adobe 公司基于 Flash Player 播放器对应的音视频 flv 封装格式提出的一种&#xff0c;基于TCP 的数据传输协议。本身具有稳定、兼容性强、高穿透的特点。常被应用于流媒体直播、点播等场景。常用于推…

计算机网络----基本概念

基本概念 在这一章从整体上介绍计算机网络的概况, 为后续的学习搭建起整体的框架; 介绍计算机网络中的基础术语和概念; 什么是因特网 『 因特网 』是一个世界范围内互联了数以亿计的计算设备的计算机网络; 因特网具体构成 因特网互联了数以亿计的计算设备, 这些设备被称为…

CKA认证 | Day4 K8s管理应用生命周期(下)

第四章 K8s管理应用程序生命周期&#xff08;下&#xff09; 1、Pod对象 1.1 Pod 的基本概念 Pod 是 Kubernetes 中最基本和最重要的概念之一&#xff0c;是一个逻辑抽象概念&#xff0c;Kubernetes创建和管理的最小单元&#xff0c; 一个Pod由一个容器或多个容器组成。它简…

【微服务】Nacos

一、安装 1、官网地址&#xff1a;https://nacos.io/download/nacos-server/ 2、启动&#xff1a;找到bin目录下的startup.cmd双击启动&#xff0c;或者打开一个命令窗口输入&#xff1a; startup.cmd -m standalone双击启动后如下&#xff1a;可以访问控制台地址 访问后的…

学习笔记032——Spring学习笔记

文章目录 一、Spring开发步骤二、Spring配置文件1、Bean标签基本配置2、Bean标签范围配置3、Bean生命周期配置4、Bean实例化三种方式5、Bean的依赖注入概念6、Bean的依赖注入方式【第一种&#xff1a;set方法注入】【第二种&#xff1a;构造方法注入】 7、Bean的依赖注入的数据…

某科技研发公司培训开发体系设计项目成功案例纪实

某科技研发公司培训开发体系设计项目成功案例纪实 ——建立分层分类的培训体系&#xff0c;加强培训跟踪考核&#xff0c;促进培训成果实现 【客户行业】科技研发行业 【问题类型】培训开发体系 【客户背景】 某智能科技研发公司是一家专注于智能科技、计算机软件技术开发与…

Elasticsearch:Retrievers 介绍

检索器&#xff08;retrievers&#xff09;是 Elasticsearch 中搜索 API 中添加的新抽象层。它们提供了在单个 _search API 调用中配置多阶段检索管道的便利。此架构通过消除对复杂搜索查询的多个 Elasticsearch API 调用的需求&#xff0c;简化了应用程序中的搜索逻辑。它还减…

Python学习34天

import random class Game: peo0 rob0 # # def __init__(self,peo,rob): # self.peopeo # self.robrob def Play(self): """ 石头剪刀布游戏&#xff0c;0代表石头&#xff0c;1代见到&#xff0c;2代表石头 …

hive的存储格式

1&#xff09; 四种存储格式 hive的存储格式分为两大类&#xff1a;一类纯文本文件&#xff0c;一类是二进制文件存储。 Hive支持的存储数据的格式主要有&#xff1a;TEXTFILE、SEQUENCEFILE、ORC、PARQUET 第一类&#xff1a;纯文本文件存储 textfile: 纯文本文件存储格式…

solr 远程命令执行 (CVE-2019-17558)

目录 漏洞描述 执行漏洞py脚本&#xff0c;取得shell连接 EXP 漏洞描述 Apache Velocity是一个基于Java的模板引擎&#xff0c;它提供了一个模板语言去引用由Java代码定义的对象。Velocity是Apache基金会旗下的一个开源软件项目&#xff0c;旨在确保Web应用程序在表示层和业…