leetcode 面试经典 150 题:合并两个有序数组
链接 | 合并两个有序数组 |
---|---|
题序号 | 88 |
题型 | 数组 |
解题方法 | 1. 双指针法 ;2. 合并+排序法 |
难度 | 简单 |
熟练度 | ✅✅✅✅✅ |
题目
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。
注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。
示例 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]
解释:需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0仅仅是为了确保合并结果可以顺利存放到 nums1 中。提示:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200 1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109进阶:你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗?
题解
合并+排序法
- 核心要点:可以直接将nums2数组放到nums1数组后面,然后直接重新排序即可以完成非递减排序的新数组。
- 时间复杂度:合并O(n);排序(快排)O((m+n)log(m+n))
- 空间复杂度:O(log(m+n))
- c++ 实现算法:
class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {for(int i = 0; i < n; i++){nums1[m+i] = nums2[i];}sort(nums1.begin(), nums1.end());}
};
双指针法
- 核心要点:考虑两个数组本身已经排序,可以利用双指针法p1、p2分别指向nums1、nums2数组索引,判定二者大小,小者放入新数组中即可。
- 时间复杂度:O(m+n)
- 空间复杂度:O(m+n)
- c++ 实现算法:
class Solution2 {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n){int p1 = 0;int p2 = 0;int sorted[m+n];int cur;while(p1 < m || p2 < n){if(p1 == m){cur = nums2[p2++]; //nums1处理完,则处理nums2}else if(p2 == n){cur = nums1[p1++]; //nums2处理完,则处理nums1}//nums1和nums2都有元素,则比较二者大小else if(nums1[p1] < nums2[p2]){cur = nums1[p1++];}else {cur = nums2[p2++];}sorted[p1+p2-1] = cur;}for(int num = 0; num < m+n; num++){nums1[num] = sorted[num];}}
};
- 演示:以示例1为例
推理:nums1[6] = {1, 2, 3, 0, 0, 0}nums2[3] = {2, 5, 6};m=6-3=3, n=3p1=0,p2=0, sorteed[6]第一次whilewhile(P1 < 3 || P2 <3)if(p1 == 3)/不成立else if(p2 == 3) //不成立else if(nums1[p1] < nums2[p2]) //1<2,成立cur = nums1[P1] /P1=0P1++else //不成立sorted[P1+P2-1] = sorted[1+0-1] = sorted[0] = cur = 1第二次while
while(P1 < 3 || P2 <3)if(p1 == 3)/不成立else if(p2 == 3) //不成立else if(nums1[p1] < nums2[p2]) //2<2,不成立else //成立cur = nums2[p2] //p2=0p2++sorted[P1+P2-1] = sorted[1+1-1] = sorted[1] = cur = 2第三次while
while(P1 < 3 || P2 <3)if(p1 == 3)/不成立else if(p2 == 3) //不成立else if(nums1[p1] < nums2[p2]) //2<5,成立cur = nums1[P1] /P1=1P1++else //不成立sorted[P1+P2-1] = sorted[2+1-1] = sorted[2] = cur = 2
以此类推。。。
完整demo
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;//合并排序法
class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {for(int i = 0; i < n; i++){nums1[m+i] = nums2[i];}sort(nums1.begin(), nums1.end());}
};//双指针法
class Solution2 {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n){int p1 = 0;int p2 = 0;int sorted[m+n];int cur;while(p1 < m || p2 < n){if(p1 == m){cur = nums2[p2++]; //nums1处理完,则处理nums2}else if(p2 == n){cur = nums1[p1++]; //nums2处理完,则处理nums1}//nums1和nums2都有元素,则比较二者大小else if(nums1[p1] < nums2[p2]){cur = nums1[p1++];}else {cur = nums2[p2++];}sorted[p1+p2-1] = cur;}for(int num = 0; num < m+n; num++){nums1[num] = sorted[num];}}
};
int main() {vector<int> nums1 = {1, 2, 3, 0, 0, 0};vector<int> nums2 = {2, 5, 6};int m = nums1.size() - 3;int n = nums2.size();Solution solution2;solution2.merge(nums1, m, nums2, n);cout << "Merged array: " << endl;for(int i = 0; i < nums1.size(); i++) {cout << "nums1[" << i << "]: " << nums1[i] << endl;}cout << endl;return 0;}
相关文章:
leetcode 面试经典 150 题:合并两个有序数组
链接合并两个有序数组题序号88题型数组解题方法1. 双指针法 ;2. 合并排序法难度简单熟练度✅✅✅✅✅ 题目 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 …...
波动理论、传输线和S参数网络
波动理论、传输线和S参数网络 传输线 求解传输线方程 对于传输线模型,我们通常用 R L G C RLGC RLGC 来表示: 其中 R R R 可以表示导体损耗,由于电子流经非理想导体而产生的能量损耗。 G G G 表示介质损耗,由于非理想电介质…...
YOLO11改进-注意力-引入自调制特征聚合模块SMFA
本篇文章将介绍一个新的改进机制——SMFA(自调制特征聚合模块),并阐述如何将其应用于YOLOv11中,显著提升模型性能。随着深度学习在计算机视觉中的不断进展,目标检测任务也在快速发展。YOLO系列模型(You Onl…...
uniapp登录
第一步整登录 先整个appid APPID和APPSecret https://developers.weixin.qq.com/community/develop/article/doc/000ca4601b8f70e379febac985b413 一个账号只能整一个小程序 正确流程 调用uni.login https://juejin.cn/post/7126553599445827621 https://www.jb51.net/a…...
mysql,数据库主从同步搭建
1.mysql主从同步1.主从同步原理(1)复现binlog日志中的sql语句(2)主服务器启动binlog日志(3)从服务器启动binlog日志,io线程,sql线程2.主从同步结构一主一从一主多从级联复制互为主从(keepalived高可用)3.mysql复制模式异步复制:主服务器处理完sql直接返回给客户端结果半同步复制…...
云途领航:现代应用架构助力企业转型新篇
在数字化转型的浪潮中,现代应用架构为企业带来了灵活性、效率和创新能力。各类服务模型相继出现,为企业提供了强有力的支持,助力其顺利转型。随着技术的快速发展,企业面临的挑战和机遇也在不断演变,这促使它们必须重新…...
redis——岁月云实战
单线程序,基于IO多路复用,基于内存和c语言编写,性能高。redis官方命令 1 数据结构 1.1 key的层级 redis的key可以通过冒号(:)来划分层级,如下图mms:company:order,但系统中可以看到有不少没有…...
Flink调优----资源配置调优与状态及Checkpoint调优
目录 第 1 章 资源配置调优 1.1 内存设置 1.1.1 TaskManager 内存模型 1、内存模型详解 2、案例分析 1.1.2 生产资源配置示例 1.2 合理利用 cpu 资源 1.2.1 使用 DefaultResourceCalculator 策略 1.2.2 使用 DominantResourceCalculator 策略 1.2.3 使用 DominantRes…...
Java web的发展历史
目录 前言: 一.Model I和Model II 1.Model I开发模式 编辑 2.Model II开发模式 二. MVC模式 前言: 该篇文章主要介绍了Java web的发展历史,以及MVC相关内容 一.Model I和Model II 1.Model I开发模式 Model1的开发模式是ÿ…...
面向微服务的Spring Cloud Gateway的集成解决方案:用户登录认证与访问控制
🎯导读:本文档详细描述了一个基于Spring Cloud Gateway的微服务网关及Admin服务的实现。网关通过定义路由规则,利用负载均衡将请求转发至不同的后端服务,并集成了Token验证过滤器以确保API的安全访问,同时支持白名单路…...
MongoDB 更新文档
关于MongoDB更新文档的操作,可以通过多种方法实现。以下是一些常用的方法: updateOne() 方法:用于更新匹配过滤器的单个文档。其语法为 db.collection.updateOne(filter, update, options)。其中,filter 用于查找文档的查询条件&a…...
静态路由与动态路由
静态路由和动态路由是网络中两种不同的路由配置方式,它们在网络中的运作方式、配置方法以及适用场景等方面存在显著差异。以下是对两者的详细比较: 一、定义与配置方式 静态路由 定义:静态路由是由网络管理员手动配置的固定路径,…...
leetcode hot二叉树的层序遍历
102. 二叉树的层序遍历 已解答 中等 相关标签 相关企业 给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点) # Definition for a binary tree node. # class TreeNode(object): # …...
Windows下ESP32-IDF开发环境搭建
Windows下ESP32-IDF开发环境搭建 文章目录 Windows下ESP32-IDF开发环境搭建一、软件安装二、搭建IDF开发环境2.1 安装VS Code插件:2.2 配置ESP-IDF插件:2.3 下载例程源码: 三、编译和烧录代码四、Windows下使用命令行编译和烧录程序4.1 配置环…...
基于高云GW5AT-15 FPGA的SLVS-EC桥MIPI设计方案分享
作者:Hello,Panda 一、设计需求 设计一个4Lanes SLVS-EC桥接到2组4lanes MIPI DPHY接口的电路模块: (1)CMOS芯片:IMX537-AAMJ-C,输出4lanes SLVS-EC 4.752Gbps Lane速率; (2&…...
【day18】多线程高级应用
day17回顾 在深入探讨模块18之前,让我们回顾一下【day17】中的关键内容: 创建多线程: 继承Thread类: 定义一个类,继承Thread。重写run方法,设置线程任务。创建自定义线程对象。调用start方法,开…...
Python接口自动化测试的实现
1)环境准备: 接口测试的方式有很多,比如可以用工具(jmeter,postman)之类,也可以自己写代码进行接口测试,工具的使用相对来说都比较简单,重点是要搞清楚项目接口的协议是什么,然后有针对性的进行选择&#x…...
nvidia docker, nvidia docker2, nvidia container toolkits区别
背景 在docker容器中用GPU时,查阅了网上许多教程,教程之间概念模糊不清,相互矛盾,过时的教程和新的教程混杂在一起。主要原因是Nvidia为docker容器的支持发生了好几代变更,api发生了不少变化。下面来总结一下各代支持…...
字节跳动Java开发面试题及参考答案(综合篇)
HTTP 与 HTTPS 的区别? HTTP(超文本传输协议)和 HTTPS(超文本传输安全协议)主要有以下区别。 从安全性角度看,HTTP 是明文传输协议,数据在网络中传输时是以原始文本的形式发送的。这就好比在信件传递过程中没有进行密封,任何中间节点(如路由器、代理服务器等)都可以查…...
搭建Elastic search群集
一、实验环境 二、实验步骤 Elasticsearch 是一个分布式、高扩展、高实时的搜索与数据分析引擎Elasticsearch目录文件: /etc/elasticsearch/elasticsearch.yml#配置文件 /etc/elasticsearch/jvm.options#java虚拟机 /etc/init.d/elasticsearch#服务启动脚本 /e…...
深入解析 Spring WebFlux:原理与应用
优质博文:IT-BLOG-CN WebFlux 是 Spring Framework 5 引入的一种响应式编程框架,和Spring MVC同级,旨在处理高并发和低延迟的非阻塞应用。这是一个支持反应式编程模型的新Web框架体系。 顺便一提,Spring Cloud Gateway在实现上是…...
Docker 部署 SpringBoot VUE项目
是一套基于若依的wms仓库管理系统 一、后端部署 后端地址:https://gitee.com/zccbbg/wms-ruoyi/tree/v1/ 1、用IDEA拉代码,并修改API统一后缀 2、复制一个配置文件 application-dev.yaml,并修改里面的mysql与redis配置 3、将打包的jar上传…...
【Java基础面试题031】Java运行时异常和编译时异常之间的区别是什么?
回答重点 主要有三大区别,分别是发生时机、捕获和处理方式和设计意图 1)发生时机: 编译时异常(Checked Exception):发生在编译阶段,编译器会检查此类异常,程序必须堆这些异常进行…...
常见网络功能概述-主要拆解功能
大家觉得有意义和参考价值记得关注和点赞!!! 一、防火墙介绍 防火墙(Firewall)是一种网络安全系统,用于监控、过滤和控制进出网络的数据流量。它是一种屏障,通过策略规则来允许、限制或拒绝数…...
Chapter 3-1. Detecting Congestion in Fibre Channel Fabrics
Chapter 3. Detecting Congestion in Fibre Channel Fabrics This chapter covers the following topics: 本章包括以下主题: Congestion detection workflow. Congestion detection metrics. Congestion detection metrics and commands on Cisco MDS switches. Automatic A…...
Day13 用Excel表体验梯度下降法
Day13 用Excel表体验梯度下降法 用所学公式创建Excel表 用Excel表体验梯度下降法 详见本Day文章顶部附带资源里的Excel表《梯度下降法》,可以对照表里的单元格公式进行理解,还可以多尝试几次不同的学习率 η \eta η来感受,只需要更改学习率…...
重温设计模式--5、职责链模式
文章目录 职责链模式的详细介绍C 代码示例C示例代码2 职责链模式的详细介绍 定义与概念 职责链模式(Chain of Responsibility Pattern)是一种行为型设计模式,它旨在将请求的发送者和多个接收者解耦,让多个对象都有机会处理请求&am…...
C语言-08复合类型-结构体
一、结构体 1.结构体struct struct关键字,允许自定义复合数据类型,将不同类型的值组合在一起,这种类型称为结构体类型。 2.使用步骤 第一步:创建或声明结构体 第二步:定义结构体变量 第三步:调用并操作结…...
vue 基础学习
一、ref 和reactive 区别 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title> </head> <body><div id"app"><h1>{{Web.title}}</h1><h1&…...
Elasticsearch检索方案之一:使用from+size实现分页
前面两篇文章介绍了elasticsearch以及Kibana的安装,检索引擎以及可视化工具都已经安装完成,接下来介绍下如何使用golang的sdk实现简单的分页查询。 1、下载Elastic官方golang sdk 在讲解elasticsearch检索之前,需要先把golang的环境安装好&…...
Highcharts 饼图:数据可视化利器
Highcharts 饼图:数据可视化利器 引言 在数据可视化的领域中,饼图作为一种经典且直观的图表类型,被广泛应用于各种行业和场景中。Highcharts,作为一个功能强大且易于使用的JavaScript图表库,为我们提供了创建交互式和…...
Docker部署Sentinel
一、简介 是什么:面向分布式、多语言异构化服务架构的流量治理组件 能干嘛:从流量路由、流量控制、流量整形、熔断降级、系统自适应过载保护、热点流量防护等多个维度来帮助开发者保障微服务的稳定性 官网地址:https://sentinelguard.io/zh-c…...
后端接口设计
一、基本规范 1.URL设计 应遵循RESTful风格,使用动词名词的方式描述接口的功能。应简洁明了,易于理解和记忆。 2.请求协议及方法 使用HTTPS协议进行数据传输,保证数据在传输过程中的安全性。如无特殊情况,统一使用post方法。 …...
GitLab部署到阿里云服务器上
GitLab 是一个用于仓库管理系统的开源项目,使用Git作为代码管理工具,并在此基础上搭建起来的web服务。可通过Web界面进行访问公开的或者私人项目。它拥有与Github类似的功能,能够浏览源代码,管理缺陷和注释。 一、安装 1.创建一…...
GitLab的卸载与重装
目录 一、GitLab的卸载 二、 GitLab的安装与配置 1. 创建安装目录 2. 安装 3. 使用 3.1 初始化 3.2 创建空白项目 编辑 3.3 配置SSH 3.3.1 配置公钥 编辑 3.3.2 配置私钥 3.4 配置本地git库 一、GitLab的卸载 1. 停止gitlab sudo gitlab-ctl stop 2. 卸载…...
动态住宅IP适合哪些数据采集项目?
在数据采集的广阔天地中,动态住宅IP代理能够灵活地变换身份,帮助我们在网络世界中自由地穿梭。这种代理IP因其住宅性质和动态变化的特点,成为了许多数据采集项目的理想选择。今天,我们就来聊聊动态住宅IP代理适合哪些数据采集项目…...
Git_撤销本地commit_查找仓库中大文件
Gitee普通账号的仓库总空间限制为5G; 右上角头像,下拉—》设置/账号设置—》数据管理下的仓库空间信息即可查看空间限额和各仓库空间大小;Gitee普通账号每次推送大小不能超过100MB,否则会推送失败;当提交大小超过100MB…...
golang windows打包为linux可执行文件
使用go的交叉编译功能 set GOOSlinux set GOARCHamd64然后再执行go build 可能会报异常, 所以贴出我的go env配置仅供参考 go env环境配置 D:\GoWork\src\go-tzv>go env set GO111MODULEauto set GOARCHamd64 set GOBIN …...
源码分析之Openlayers中GeometryCollection类
概述 本文主要介绍GeometryCollection类,GeometryCollection类继承于Geometry类,关于Geometry类,参考这篇文章源码分析之Openlayers中Geometry基类介绍 GeometryCollection类就是一组几何对象的集合. 源码分析 GeometryCollection类源码实现 GeometryCollection类源码实现…...
*【每日一题 基础题】 [蓝桥杯 2024 省 B] 好数
[蓝桥杯 2024 省 B] 好数 好数 一个整数如果按从低位到高位的顺序,奇数位(个位、百位、万位……)上的数字是奇数,偶数位(十位、千位、十万位……)上的数字是偶数,我们就称之为“好数”。 给定一…...
Redis大Key问题全解析
1. 引言 1.1 什么是Redis大Key? Redis大Key是指单个Key对应的数据量过大,占用过多的内存或导致操作耗时较长的现象。大Key可以是以下几种常见数据类型中的任意一种: String类型:单个字符串的长度过大。List类型:包含…...
一起学Git【第六节:查看版本差异】
git diff是 Git 版本控制系统中用于展示差异的强大工具。他可以用于查看文件在工作区、暂存区和版本库之间的差异、任意两个指定版本之间的差异和两个分支之间的差异等,接下来进行详细的介绍。 1.显示工作区与暂存区之间的差异 # 显示工作区和暂存区之间的差异,后面不加参数…...
USB Hub 检测设备
系列文章目录 xHCI 简单分析 USB Root Hub 分析 USB Hub 检测设备 文章目录 系列文章目录一、引言二、hub_eventshub_port_connect_changeusb_alloc_devusb_set_device_statehub_port_initusb_new_device 一、引言 USB Hub 检测设备 一文中讲到,当有 USB 插入时&…...
Python 正则表达式
正则在线实用工具:regex101 正则表达式(regular expression)是一种用于匹配字符串中字符组合模式的工具。它可以用来检查一个字符串是否匹配某个模式、提取字符串中的信息、替换字符串中的某些部分等。 Python 的 re 模块提供了对正则表达式…...
【Mac】终端改色-让用户名和主机名有颜色
效果图 配置zsh 1.打开终端,进入.zshrc配置 cd ~ vim .zshrc2.添加如下配置并保存 # 启用命令行颜色显示 export CLICOLOR1 ## 加载颜色支持 autoload -U colors && colors # 配置 zsh 提示符 PROMPT"%{$fg_bold[red]%}%n%{$reset_color%}%{$fg_bol…...
React 前端框架入门
这里写目录标题 React 前端框架入门什么是 React?核心特性基本概念1. JSX2. 组件3. State 和 Props4. 生命周期5. React Hooks React 应用示例项目结构如何启动 React 项目参考资料 React 前端框架入门 什么是 React? React 是由 Facebook 开发并开源的…...
复习打卡大数据篇——Hadoop YARN
目录 1.什么是yarn 2.yarn的三大角色 3.任务(MR)提交到YARN运行流程 4. 调度器Scheduler 5.YARN HA 高可用 1.什么是yarn YARN(Yet Another Resource Negotiator)是一个资源管…...
03.HTTPS的实现原理-HTTPS的工作流程
03.HTTPS的实现原理-HTTPS的工作流程 简介1. HTTPS的工作流程1.1. TCP的工作流程1.1.1. 三次握手的详细步骤1.1.2. 三次握手的作用 1.2. HTTPS的工作流程1.2.1. HTTPS与TCP的关系1.2.2. HTTPS的工作流程 2. 公钥和私钥的作用3. 对称密钥的生成和交换4. 对称加密和非对称加密的区…...
idea部署maven项目步骤(图+文)
博主介绍:专注于Java(springboot ssm 等开发框架) vue .net php phython node.js uniapp 微信小程序 等诸多技术领域和毕业项目实战、企业信息化系统建设,从业十五余年开发设计教学工作 ☆☆☆ 精彩专栏推荐订阅☆☆☆☆☆不…...
Eclipse 添加书签
Eclipse 添加书签 Eclipse 是一款非常受欢迎的集成开发环境(IDE),广泛用于 Java、C、Python 等语言的开发。在处理大型项目时,开发者通常需要在不同文件和代码行之间频繁切换。为了提高工作效率,Eclipse 提供了书签功…...