LeetCode 0088. 合并两个有序数组
【LetMeFly】88.合并两个有序数组:O(m + 1) + O(1)的做法
力扣题目链接:https://leetcode.cn/problems/merge-sorted-array/
给你两个按 非递减顺序 排列的整数数组 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 + nnums2.length == n0 <= m, n <= 2001 <= m + n <= 200-109 <= nums1[i], nums2[j] <= 109
进阶:你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗?
方法一:三指针(双指针)
这道题不返回任何值,很显然,出题者想让你在nums1数组上原地修改。
怎么原地修改呢?nums1后面全是 0 0 0,而这些地方本来应该是“大数”,所以我们使用两个指针,从 n u m s 1 nums1 nums1和 n u m s 2 nums2 nums2的大数区域往前指,每次将二者较大的那个放到nums1后面不就可以了吗。
tail↓
1 3 0 0↑
2 6↑
3 < 6 3 < 6 3<6,所以将 6 6 6放到tail处,
tail↓
1 3 0 6↑
2 -
↑
3 > 2 3 > 2 3>2,所以将 3 3 3放到tail处,
tail↓
1 - 3 6
↑
2 -
↑
1 < 2 1 < 2 1<2,所以将 2 2 2放到tail处,
tail
↓
1 2 3 6
↑
- -
n u m s 2 nums2 nums2的指针指完了,任务完成,得到 [ 1 , 2 , 3 , 6 ] [1, 2, 3, 6] [1,2,3,6]
- 时间复杂度 O ( m + n ) O(m + n) O(m+n)
- 空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C++
class Solution {
public:void merge(vector<int>& nums1, int l1, vector<int>& nums2, int l2) {int n = l1 + l2 - 1;l1--, l2--;while (l2 >= 0) {while (l1 >= 0 && nums1[l1] > nums2[l2]) {nums1[n--] = nums1[l1--];}nums1[n--] = nums2[l2--];}}
};
Python
from typing import Listclass Solution:def merge(self, nums1: List[int], l1: int, nums2: List[int], l2: int) -> None:"""Do not return anything, modify nums1 in-place instead."""l = l1 + l2 - 1l1, l2 = l1 - 1, l2 - 1while l2 >= 0:while l1 >= 0 and nums1[l1] > nums2[l2]:nums1[l] = nums1[l1]l, l1 = l - 1, l1 - 1nums1[l] = nums2[l2]l, l2 = l - 1, l2 - 1
同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/132256535
相关文章:
LeetCode 0088. 合并两个有序数组
【LetMeFly】88.合并两个有序数组:O(m 1) O(1)的做法 力扣题目链接:https://leetcode.cn/problems/merge-sorted-array/ 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2…...
定义行业新标准?谷歌:折叠屏手机可承受20万次折叠
根据Patreon账户上的消息,Android专家Mishaal Rahman透露,谷歌计划推出新的硬件质量标准,以满足可折叠手机市场的需求。Android原始设备制造商(OEM)将需要完成谷歌提供的问卷调查,并提交样品设备进行严格审…...
在vscode中配置C/C++环境GCC on Linux
https://code.visualstudio.com/docs/cpp/config-linux 官方文档 准备工作 为了能够在vs code中编译运行C/C程序,需要下载: Visual Studio Code C扩展插件,cuda,,, 对于该扩展插件,打开vs c…...
windows执行完LoadLibrary()后,可以删除源动态库文件,函数不会锁库文件
windows执行完LoadLibrary()后,可以删除源动态库文件,函数不会锁库文件。 #include <iostream> #include <Windows.h>int main() {char path[MAX_PATH]{};GetCurrentDirectoryA(sizeof(path), path);HMODULE lib LoadLibraryA("testd…...
ios 知识
IOS 类文件.h和.m中interface的区别 大家都知道我们在创建类文件时会发现: #import <UIKit/UIKit.h>interface ViewController : UIViewControllerend和 #import "ViewController.h"interface ViewController ()end那么他们之间有何区别呢&#x…...
8 | 美国航班数据分析
"在现代快节奏的生活中,航空旅行已经成为人们出行的重要方式之一。然而,航班的准时性一直以来都是旅客和航空公司关注的焦点。无论是商务出差还是休闲度假,乘客们都希望能够在既定的时间内安全、准时地到达目的地。而对于航空公司而言,准点运营不仅关乎乘客体验,还涉…...
app.use(express.json()) 使用
Express内置的中间件 自 Express 4.16.0 版本开始,Express 内置了 3 个常用的中间件,极大的提高了 Express 项目的开发效率和体验 express.static 快速托管静态资源的内置中间件,例如: HTML 文件、图片、CSS 样式等(无…...
基于PyTorch的图像识别
前言 图像识别是计算机视觉领域的一个重要方向,具有广泛的应用场景,如医学影像诊断、智能驾驶、安防监控等。在本项目中,我们将使用PyTorch来开发一个基于卷积神经网络的图像识别模型,用来识别图像中的物体。下面是要识别的四种物…...
js合并数组对象(将数组中具有相同属性对象合并到一起,组成一个新的数组)
一、根据数组对象中某一key值,合并相同key值的字段,到同一个数组对象中,组成新的数组 1.原数组: var array [{ id: 1, name: Alice },{ id: 2, name: Bob },{ id: 1, age: 25 },{ id: 3, name: Charlie, age: 30 } ];2.合并后数…...
Spring BeanPostProcessor 接口的作用和使用
BeanPostProcessor 接口是 Spring 框架中的一个扩展接口,用于在 Spring 容器实例化、配置和初始化 bean 的过程中提供自定义的扩展点。通过实现这个接口,您可以在 bean 实例创建的不同生命周期阶段插入自己的逻辑,从而实现对 bean 行为的定制…...
Android 13 Hotseat定制化修改——006 hotseat图标禁止移动到Launcher中
目录 一.背景 二.方案 三.具体实践 一.背景 客户定制需要修改让hotseat中的icon不要移动到Launcher中,所以需要进行定制 二.方案 原生的Hotseat与Launcher是可以相互移动的,然后现在的需求是Hotseat中的图标只能在Hotseat中移动,所以需要做下限制 思路:在事件拦截的地…...
RabbitMQ 发布确认机制
发布确认模式是避免消息由生产者到RabbitMQ消息丢失的一种手段 发布确认模式 原理说明实现方式开启confirm(确认)模式阻塞确认异步确认 总结 原理说明 生产者通过调用channel.confirmSelect方法将信道设置为confirm模式,之后RabbitMQ会返回Co…...
微信小程序使用rich-text解析富文本字符串的时候,遇到image标签图片很大超过屏幕
场景: 使用uniapp开发微信小程序,解析富文本文章需求 用到的组件: u-view2.0的u-parse uniapp提供的rich-text 以上两种组件都是解析富文本的作用,一般用于富文本解析场景,比如解析文章内容,商品详情&am…...
使用IIS服务器部署Flask python Web项目
参考文章 ""D:\Program Files (x86)\Python310\python310.exe"|"D:\Program Files (x86)\Python310\lib\site-packages\wfastcgi.py"" can now be used as a FastCGI script processor参考文章 请求路径填写*,模块选择FastCgiModule&…...
sentinel核心流程源码解析
sentinel的处理槽(ProcessorSlot) 可以说,sentinel实现的各种功能就是由各处理槽完成的 ,ProcessorSlot定义了四个方法: 当进入该处理槽时触发该方法 处理完 entry方法之后触发该方法 退出该处理槽时触发该方法 exit方法处理完成时触发该方法 sentinel的…...
中睿天下Coremail | 2023年第二季度企业邮箱安全态势观察
今日,中睿天下联合Coremail邮件安全发布《2023第二季度企业邮箱安全性研究报告》,对2023第二季度和2023上半年的企业邮箱的安全风险进行了分析。 一 垃圾邮件同比下降16.38% 根据监测,2023年Q2垃圾邮件数量达到6.47亿封,环比下降…...
桶排序-1184:明明的随机数
【题目描述】 明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了N个1到1000之间的随机整数(N≤100),对于其中重复的数字,只保留一个,把其余相同的数去掉&#x…...
Spring Boot中整合Keycloak OpenID Connect(OIDC)
在Spring Boot中整合Keycloak OpenID Connect(OIDC)是一个常见的任务,用于实现身份验证和授权。Keycloak是一个开源的身份和访问管理解决方案,而OpenID Connect是构建在OAuth 2.0之上的认证和授权协议。下面是一个简单的步骤指南&…...
如何使用Mac终端给树莓派pico构建C/C++程序进行开发,以及遇到各种问题该怎么处理,不使用任何IDE或编辑器(例如VS Code)
写本文的原因是官方的教程已经过时了,如果你现在按照官方教程来在 Mac 上进行配置,那么会遇到一堆问题,比如我几乎把能踩的“雷”都踩了。所以这里记录了完整过程,以及各种错误的原因和处理方法,不然以后换 Mac 了或者…...
linux 关机和重启
关机和重启 关机和重启之前最好先数据数据同步一下 # 将数据由内存同步到硬盘sync 关机 #shutdown [选项] 时间#立即进入维护模式shutdown now#立即重启shutdown -r now#20:00 重新启动计算机shutdown -r 20:00& #立即关机shutdown -h now# 20:00 关闭计算机shutdown -h 20…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...
