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…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
