【面试经典150 | 数组】合并两个有序数组
文章目录
- 写在前面
- Tag
- 题目来源
- 题目解读
- 解题思路
- 方法一:合并排序
- 方法二:双指针
- 方法三:原地操作-从前往后
- 方法四:原地操作-从后往前
- 写在最后
写在前面
本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……
专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:
- Tag:介绍本题牵涉到的知识点、数据结构;
- 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
- 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
- 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
- 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。
Tag
【双指针】【原地操作-从前往后】【原地操作-从后往前】【排序】【数组】
题目来源
面试经典 150 题——88. 合并两个有序数组

题目解读
给定两个有序数组 nums1
和 nums2
,现在需要合并两个数组到 nums1
中,nums1
中已经预留了合并的位置。
解题思路
方法一:合并排序
将数组nums2
合并到 nums1
数组中的空位上,再利用 sort()
函数进行排序。
时间复杂度: O ( ( m + n ) l o g ( m + n ) ) O((m+n)log(m+n)) O((m+n)log(m+n)),快速排序的时间复杂度。
空间复杂度: O ( l o g ( m + n ) ) O(log(m+n)) O(log(m+n)),快速排序占用的空间。
方法二:双指针
维护一个临时数组,用来存放合并后的数组。
使用两个指针 i
,j
,分别指向两数组首元素,迭代比较 i
、j
位置处元素大小,将小的元素依次存入临时数组。
最后,将临时数组中元素移植到 nums1
数组中。
时间复杂度 O ( m + n ) O(m+n) O(m+n)。
空间复杂度 O ( m + n ) O(m+n) O(m+n),因为需要一个临时数组,大小为 m + n m+n m+n。
方法三:原地操作-从前往后
首先,重新定义一下双指针 i
和 j
的含义,两指针分别表示指向数组 nums1
和 nums2
当前没有使用过的最小的元素,i
也表示当前最小元素将要放置的位置。
在方法二中,我们之所以使用了一个临时数组来存放较小的数字,是因为我们从前往后枚举比较两指针指向的元素得到较小值,如果直接合并到 nums1
数组中,可能会覆盖掉 nums1
中接下来将要比较的数字(这也是原地操作删除有序数组中的重复元素的思想,具体内容可见 图解【原地操作】删除有序数组中的重复元素)。
直接合并有问题,那么我们进行交换处理保留较大数,即交换 nums1[i]
和 nums2[j]
,交换了之后,我们将较小的数放置在数组 nums1
的 i
位置处,较大的数放置在数组 nums2
的 j
位置处。这时候还需要对数组 nums2
进行排序,每次交换数字之后都要进行排序操作。
因为我们的双指针都是指向当前数组中最小的数字,交换操作有可能破坏数组 nums2
的升序结构。
下面以图示形式进行演示:
(1)双指针从 0
位置开始;

(2)nums1[0] < nums2[0]
,右移 i
指针;

(3)nums1[1] = nums2[0]
,右移 i
指针;

(4)nums2[0] < nums1[2]
,交换数组中两元素;

(5)nums2
数组的升序结构被破坏,需要进行升序排序;

(6)nums1[2] = nums2[0]
,右移 i
指针;

(7)数组 nums1
中前半部分数位已经填充完毕,后半部分占位符使用数组 nums2
填充,当前位置填充完毕之后,同时右移两指针;如此迭代填充,直至 j
指针越界,合并两个有序数组完成!

实现代码
class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int i = 0, j = 0;while (j < n) {if (i >= m) {nums1[i] = nums2[j++];}else {if (nums1[i] > nums2[j]) {swap(nums1[i], nums2[j]);}sort(nums2.begin(), nums2.end());}++i;}}
};
时间复杂度: O ( m a x ( m , n l o g n ) ) O(max(m, nlogn)) O(max(m,nlogn))。
空间复杂度: O ( n l o g n ) O(nlogn) O(nlogn),快速排序占用的空间。
方法四:原地操作-从后往前
现在考虑从后往前处理,具体地维护三个指针,i
指向数组 nums1
比较元素的末尾即 m-n-1
位置,j
指针指向数组 nums2
比较元素的末尾即 n-1
位置,k
指针指向数组 nums1
的末尾即 m-1
位置。
我们比较 nums1[i]
和 nums2[j]
元素大小,将较大的元素放置在数组 nums1
的 k
位置处。
下面以图示形式进行演示:
(1)三指针初始化;

(2)nums1[2] < nums2[2]
,将较大的 nums2[2]
放置在 tail
处;

(3)j
、tail
指针分别左移一个单位,为下次比较做准备;

(4) nums1[2] < nums2[1]
,将较大的 nums2[1]
放置在 tail
处;

(5)j
、tail
指针分别左移一个单位,为下次比较做准备;

(6)nums1[2] = nums2[0]
,将 nums1[1]
放置在 tail
处;

(7)i
、tail
指针分别左移一个单位,为下次比较做准备;

(8)nums1[1] < nums2[0]
,将较大的 nums2[0]
放置在 tail
处;

(9)j
、tail
指针分别左移一个单位,j
指针越界,原地操作结束,数组 nums1
为最后合并后的数组。

实现代码
class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int i = m - 1, j = n - 1, k = m + n - 1;while (i >= 0 && j >= 0) {if (nums2[j] > nums1[i]) {nums1[k--] = nums2[j--];}else {nums1[k--] = nums1[i--];}}while (j >= 0) {nums1[k--] = nums2[j--];}}
};
时间复杂度: O ( m + n ) O(m+n) O(m+n)。
空间复杂度: O ( 1 ) O(1) O(1),原地操作,仅仅使用了三个指针变量。
写在最后
如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。
最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。
相关文章:

【面试经典150 | 数组】合并两个有序数组
文章目录 写在前面Tag题目来源题目解读解题思路方法一:合并排序方法二:双指针方法三:原地操作-从前往后方法四:原地操作-从后往前 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章…...

系统架构设计专业技能 ·操作系统
现在的一切都是为将来的梦想编织翅膀,让梦想在现实中展翅高飞。 Now everything is for the future of dream weaving wings, let the dream fly in reality. 点击进入系列文章目录 系统架构设计高级技能 操作系统 一、操作系统概述二、进程管理2.1 进程概念2.2 进…...

CSP 202209-1 如此编码
答题 题目就是字多 #include<iostream>using namespace std;int main() {int n,m;cin>>n>>m;int a[n],c[n1];c[0]1;for(int i0;i<n;i){cin>>a[i];c[i1]c[i]*a[i];}for(int i0;i<n;i){cout<<(m%c[i1]-m%c[i])/c[i]<< ;} }...

windows安装向量数据库milvus
本文介绍windows下安装milvus的方法。 一.Docker安装 1.1docker下载 首先到Docker官网上下载docker:Docker中文网 官网 1.2.安装前前期准备 先使用管理员权限打开windows powershell 然后在powershell里面输入下面那命令,启用“适用于 Linux 的 Windows 子系统”…...
Qt中,QScript对JavaScript的内置接口支持情况
支持 JSON.parse()/stringify() Object.keys() 不支持 console.info()/debug()/warn()/error() window setTimeout() clearTimeout() setInterval() clearInterval() 后续添加更多接口支持情况~...
C语言基础-typedef的用法
文章目录 前言基础用法高阶用法typedef作用于数组typedef作用于函数指针 总结 前言 熟悉C语言的同学,应该都见过typedef,但可能对typedef的用法并不是真的了解。本文介绍几种typedef的用法,相信会有所帮助 基础用法 一般typedef用来声明一个…...

Linux中安装MySQL5.7.42
1. 首先,下载mysql5.7.42的安装包(下方是下载地址),选择红色框框的下载(注意的是,这个链接只提供5.7的版本下载,可能还会更新,不一定打开就是5.7.42的版本,后续可能会有4…...
网络基础--1.网络纵横
网络的发展历程 计算机由原来的只能单一处理信息(单用户批处理)逐步发展为多用户批处理,可以实现一台计算机连接多个终端同时使用一台计算机(分时系统),但是多个终端之间不能相互通信,再发展成为…...
Django TypeError: Abstract models cannot be instantiated.错误解决方案
问题 [2023-09-05 10:23:41][dvadmin.utils.exception.CustomExceptionHandler():64] [ERROR] Traceback (most recent call last): File “D:\InstallSpace\Anaconda3\envs\py39\lib\site-packages\rest_framework\views.py”, line 506, in dispatch response handler(requ…...

vscode使用delve调试golang程序
环境配置 delve仓库,含有教程:https://github.com/go-delve/delve golang的debugging教程:https://github.com/golang/vscode-go/wiki/debugging > go version go version go1.20 windows/amd64> go install github.com/go-delve/de…...

如何从任何苹果、Windows或安卓设备访问iCloud照片
本文介绍了如何在各种设备上访问iCloud照片库,包括iPhone和iPad、Mac、Windows PC和Android设备。说明适用于iOS 13及以上版本、iPadOS 13及以上、macOS Big Sur(10.16)和Catalina(10.15)、Windows 10或11以及Android 10。 从iPhone、iPod Touch和iPad访问iCloud照片 照…...

关于“找不到mfc140u.dll,无法继续执行代码”问题的分析处理方法
我想和大家分享一个在编程过程中经常会遇到的问题——找不到mfc140u.dll,无法继续执行代码。找不到 mfc140u.dll,这个问题可能会让我们感到困扰。mfc140u.dll 是 Microsoft Foundation Classes(MFC)库的一部分,它是一个 Windows 系…...
用 TripletLoss 优化bert ranking
下面是 用 TripletLoss 优化bert ranking 的demo import torch from torch.utils.data import DataLoader, Dataset from transformers import BertModel, BertTokenizer from sklearn.metrics.pairwise import pairwise_distancesclass TripletRankingDataset(Dataset):def __…...
Tomcat安装及使用
这里写目录标题 Tomcat一.java基础1.java历史2.java组成3.实现动态网页功能serveltjsp 4.jdkJDK 和 JRE 关系安装openjdk安装oracle官方JDK 二.tomcat基础功能1.Tomcat介绍2.安装tomcat二进制安装Tomcat 3.配置文件介绍及核心组件配置文件组件 4.状态页5.常见的配置详解6.tomca…...

法国新法案强迫 Firefox 等浏览器审查网站
导读Mozilla 基金会已发起了一份请愿书,旨在阻止法国政府强迫 Mozilla Firefox 等浏览器审查网站。 据悉,法国政府正在制定一项旨在打击网络欺诈的 SREN 法案 (“Projet de loi Visant scuriser et reguler lespace numrique”),包含大约 2…...

开源电商项目 Mall:构建高效电商系统的终极选择
文章目录 Mall 项目概览前台商城系统后台管理系统系统架构图业务架构图 模块介绍后台管理系统 mall-admin商品管理:功能结构图-商品订单管理:功能结构图-订单促销管理:功能结构图-促销内容管理:功能结构图-内容用户管理࿱…...

QT(9.1)对话框与事件处理
作业: 1. 完善登录框 点击登录按钮后,判断账号(admin)和密码(123456)是否一致,如果匹配失败,则弹出错误对话框,文本内容“账号密码不匹配,是否重新登录”&…...

C++项目实战——基于多设计模式下的同步异步日志系统-③-前置知识补充-设计模式
文章目录 专栏导读六大原则单例模式饿汉模式懒汉模式 工厂模式简单工厂模式工厂方法模式抽象工厂模式 建造者模式代理模式 专栏导读 🌸作者简介:花想云 ,在读本科生一枚,C/C领域新星创作者,新星计划导师,阿…...
C++ 新旧版本两种读写锁
一、简介 读写锁(Read-Write Lock)是一种并发控制机制,用于多线程环境中实现对共享资源的高效读写操作。读写锁允许多个线程同时读取共享资源,但在有写操作时,需要互斥地独占对共享资源的访问,以确保数据的…...
ES6 字符串的repeat()方法
repeat() 方法返回一个新字符串,表示将原字符串重复n次 格式:str.repeat(n) 参数n:str需要重复多少次 参数n的取值: n是正整数: x.repeat(3) // 输出结果:"xxx" hello.repeat(2) // 输出结果…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...

MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...

Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...