力扣面试150题 | 88.合并两个有序数组
力扣面试150题 | 88.合并两个有序数组
- 题目描述
- 解题思路
- 代码实现
- 复杂度分析
题目描述
88.合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 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
解题思路
整体思路是从后向前更新数组,让一个指针i指向nums1有意义元素的末尾,也就是i = m - 1,另一个指针j指向nums2的末尾,即j = n - 1,第三个指针k指向nums1的末尾,即k = m + n - 1。
随后遍历指针i和指针j,对比nums[i]和nums[j],让k指向较大的那个,随着i和j的遍历,k也递减,从而达到让指针k在原数组的基础上重新构造出一个数组。
代码实现
class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int i = m - 1;int j = n - 1;int k = m + n - 1;while (j >= 0){ // 让j遍历完if (i >= 0 && nums1[i] > nums2[j]) {nums1[k--] = nums[i--];} else {nums1[k--] = nums[j--];}}}
};
复杂度分析
- 时间复杂度:O(m+n)
- 空间复杂度:O(1)
相关文章:
力扣面试150题 | 88.合并两个有序数组
力扣面试150题 | 88.合并两个有序数组 题目描述解题思路代码实现复杂度分析 题目描述 88.合并两个有序数组 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并…...
Spring Cache快速入门教程及案例
1. Spring Cache介绍 Spring Cache提供了一组注解,使开发者能够轻松地在方法上定义缓存行为 Spring Cache抽象了缓存的底层实现,允许开发者选择使用不同的缓存提供者(如 Ehcache、Redis、Caffeine 等)。通过配置相应的缓存管理器…...
pycharm中debug,py文件
1、先把需要的实参传入 2、在合适位置打上断点 3、在小三角旁边右键调用调试 4.步进/步出查看 5.选择单步执行,走的更慢...
虚拟化之指令的Trap和仿真
有时,虚拟机监控程序需要在虚拟机(VM)中模拟操作。例如,VM内的软件可能尝试配置与功耗管理或缓存一致性相关的低级处理器控件。通常,您不希望将VM直接访问这些控件,因为它们可能被用于突破隔离,或影响系统中的其他VM。 trap在执行给定操作(例如读取寄存器)时引发异常…...
Python函数默认参数设置
在某些情况下,程序需要在定义函数时为一个或多个形参指定默认值,这样在调用函数时就可以省略为该形参传入参数值,而是直接使用该形参的默认值。 为形参指定默认值的语法格式如下: 形参名 默认值 从上面的语法格式可以看出&…...
js moment计算当前时间到24:00:00的剩余时间
2023.12.7今天我学习了如何计算当前的时间到24:00:00剩下的时间,https://momentjs.cn/ const now moment(); // 获取当前时间const endOfDay moment().endOf(day); // 设置当天的 23:59:59const duration moment.duration(endOfDay.diff(now)); // 计算剩余时间的…...
【UE5】瞬移+马赛克过渡效果
效果 步骤 1. 新建一个工程,创建一个Basic关卡 2. 添加第三人称游戏资源到内容浏览器 3. 新建一个材质,这里命名为“M_Pixel” 打开“M_Pixel”,设置材质域为“后期处理” 在材质图表中添加如下节点 此时效果如下,已经有马赛克的…...
【Skynet 入门实战练习】分布式 ID | 雪花算法 | 缓存设计 | LRU算法 | 数据库
文章目录 前言雪花算法LRU 算法缓存模块数据库测试逻辑 前言 本节实现了 分布式 ID 生成系统,采用雪花算法实现唯一 ID;实现缓存架构,采用 LRU (最近最少使用)算法。 雪花算法 分布式 ID 生成算法的有很多种&#x…...
ArcGIS Pro中怎么设置标注换行
在ArcGIS Pro中进行文字标注的时候,如果标注的字段内容太长,直接标注的话会不美观,而且还会影响旁边的标注显示,这里为大家介绍一下在ArcGIS Pro中设置文字换行的方法,希望能对你有所帮助。 数据来源 本教程所使用的…...
MAX26——快速人物毛发插片工具 Hair cards tool
一提到毛发插件,我们一般想起的就是maya的 xgrn 或者max的ox。但是这些都是我们做影视级数字人用的。比较费性能也比较费面 下面分享一个干货 Hair cards tool 这个插件操作不像xgen与ox那么复杂。基本上0基础上手5分钟不到。就能插片出不错的效果。比较适用于&…...
一天一个设计模式---原型模式
基本概念 原型模式(Prototype Pattern)是一种创建型设计模式,其主要目的是通过复制现有对象来创建新对象,而不是通过实例化类。原型模式允许在运行时动态创建对象,同时避免了耦合与子类化。 在原型模式中࿰…...
<习题集><LeetCode><链表><2/19/21/23/24>
目录 2. 两数相加 19. 删除链表的倒数第 N 个结点 21. 合并两个有序链表 23. 合并 K 个升序链表 24. 两两交换链表中的节点 2. 两数相加 https://leetcode.cn/problems/add-two-numbers/ public ListNode addTwoNumbers(ListNode l1, ListNode l2) {//head是cur链表头节点…...
C++实现DFS、BFS、Kruskal算法和Prim算法、拓扑排序、Dijkstra算法
背景: 实现要求: 根据图的抽象数据类型的定义,请采用邻接矩阵来存储图1,采用邻接表来存储图2,并完成如下操作:对图1无向图进行深度优先遍历和广度优先遍历。对图1无向图采用Kruskal算法和Prim算法得出最小…...
Spring 依赖注入的三种方式优缺点
小王学习录 前言属性注入1. 属性注入的优点2. 属性注入的缺点 Setter注入Setter注入的优点Setter注入的缺点 构造方法注入1. 构造方法的优点 总结补充Aurowired注解和Resource注解的区别 前言 在前面的文章中介绍了基于注解的方式将Bean存储到Spring中, 接下来介绍如何基于注解…...
代理模式介绍(静态代理、jdk动态代理、cglib代理)
一、静态代理 (一)定义 1、定义 为其他对象提供一种代理以控制对这个对象的访问; 2、涉及到的角色 (1)抽象主题角色:真实主题和代理主题的共同接口,便于在使用真实主题的地方都可以使用代理…...
设计模式基础——工厂模式剖析(2/2)
目录 一、工厂模式 1.1 工厂模式的定义 1.2 工厂模式的设计意图 1.3 工厂模式主要解决的问题 1.4 工厂模式的缺点 1.5 实际的应用案例 1. 数据库连接池 2. 图形用户界面(GUI)组件 3. 文件操作 二、各种工厂模式的变形 1.1 简单工厂模式&#…...
spark3.x 读取hudi报错
报错信息如下: Exception in thread "main" org.apache.hudi.exception.HoodieUpsertException: Failed to upsert for commit time 20231201203145254 at org.apache.hudi.table.action.commit.BaseWriteHelper.write(BaseWriteHelper.java:64) at org.apa…...
微信小程序中block和View组件的使用区别
block和View组件都是用于布局的组件: 1. Block组件: Block组件是一个无实际显示效果的组件,它主要用于包裹一组组件,并提供了类似于div的作用。使用Block组件可以将一组组件进行分组,便于样式的管理和控制。Block组件不会在页面…...
代码混淆技术探究与工具选择
代码混淆技术探究与工具选择 引言 在软件开发中,保护程序代码的安全性是至关重要的一环。代码混淆(Obfuscated code)作为一种常见的保护手段,通过将代码转换成难以理解的形式来提升应用被逆向破解的难度。本文将介绍代码混淆的概…...
selenium 解决 id定位、class定位中,属性值带空格的解决办法
一、前置说明 selenium遇到下面这种元素: <th id"demo id" class"value1 value2 value3 ">1、虽然id一般不会有空格,但是前端错误的这种写法(如下图),会造成使用id定位不到元素,如: find…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
