当前位置: 首页 > news >正文

LeetCode 0088. 合并两个有序数组

【LetMeFly】88.合并两个有序数组:O(m + 1) + O(1)的做法

力扣题目链接:https://leetcode.cn/problems/merge-sorted-array/

给你两个按 非递减顺序 排列的整数数组 nums1 nums2,另有两个整数 mn ,分别表示 nums1nums2 中的元素数目。

请你 合并 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) 的算法解决此问题吗?

方法一:三指针(双指针)

这道题不返回任何值,很显然,出题者想让你在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.合并两个有序数组&#xff1a;O(m 1) O(1)的做法 力扣题目链接&#xff1a;https://leetcode.cn/problems/merge-sorted-array/ 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2&#xff0c;另有两个整数 m 和 n &#xff0c;分别表示 nums1 和 nums2…...

定义行业新标准?谷歌:折叠屏手机可承受20万次折叠

根据Patreon账户上的消息&#xff0c;Android专家Mishaal Rahman透露&#xff0c;谷歌计划推出新的硬件质量标准&#xff0c;以满足可折叠手机市场的需求。Android原始设备制造商&#xff08;OEM&#xff09;将需要完成谷歌提供的问卷调查&#xff0c;并提交样品设备进行严格审…...

在vscode中配置C/C++环境GCC on Linux

https://code.visualstudio.com/docs/cpp/config-linux 官方文档 准备工作 为了能够在vs code中编译运行C/C程序&#xff0c;需要下载&#xff1a; Visual Studio Code C扩展插件&#xff0c;cuda&#xff0c;&#xff0c;&#xff0c; 对于该扩展插件&#xff0c;打开vs c…...

windows执行完LoadLibrary()后,可以删除源动态库文件,函数不会锁库文件

windows执行完LoadLibrary()后&#xff0c;可以删除源动态库文件&#xff0c;函数不会锁库文件。 #include <iostream> #include <Windows.h>int main() {char path[MAX_PATH]{};GetCurrentDirectoryA(sizeof(path), path);HMODULE lib LoadLibraryA("testd…...

ios 知识

IOS 类文件.h和.m中interface的区别 大家都知道我们在创建类文件时会发现&#xff1a; #import <UIKit/UIKit.h>interface ViewController : UIViewControllerend和 #import "ViewController.h"interface ViewController ()end那么他们之间有何区别呢&#x…...

8 | 美国航班数据分析

"在现代快节奏的生活中,航空旅行已经成为人们出行的重要方式之一。然而,航班的准时性一直以来都是旅客和航空公司关注的焦点。无论是商务出差还是休闲度假,乘客们都希望能够在既定的时间内安全、准时地到达目的地。而对于航空公司而言,准点运营不仅关乎乘客体验,还涉…...

app.use(express.json()) 使用

Express内置的中间件 自 Express 4.16.0 版本开始&#xff0c;Express 内置了 3 个常用的中间件&#xff0c;极大的提高了 Express 项目的开发效率和体验 express.static 快速托管静态资源的内置中间件&#xff0c;例如&#xff1a; HTML 文件、图片、CSS 样式等&#xff08;无…...

基于PyTorch的图像识别

前言 图像识别是计算机视觉领域的一个重要方向&#xff0c;具有广泛的应用场景&#xff0c;如医学影像诊断、智能驾驶、安防监控等。在本项目中&#xff0c;我们将使用PyTorch来开发一个基于卷积神经网络的图像识别模型&#xff0c;用来识别图像中的物体。下面是要识别的四种物…...

js合并数组对象(将数组中具有相同属性对象合并到一起,组成一个新的数组)

一、根据数组对象中某一key值&#xff0c;合并相同key值的字段&#xff0c;到同一个数组对象中&#xff0c;组成新的数组 1.原数组&#xff1a; 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 框架中的一个扩展接口&#xff0c;用于在 Spring 容器实例化、配置和初始化 bean 的过程中提供自定义的扩展点。通过实现这个接口&#xff0c;您可以在 bean 实例创建的不同生命周期阶段插入自己的逻辑&#xff0c;从而实现对 bean 行为的定制…...

Android 13 Hotseat定制化修改——006 hotseat图标禁止移动到Launcher中

目录 一.背景 二.方案 三.具体实践 一.背景 客户定制需要修改让hotseat中的icon不要移动到Launcher中,所以需要进行定制 二.方案 原生的Hotseat与Launcher是可以相互移动的,然后现在的需求是Hotseat中的图标只能在Hotseat中移动,所以需要做下限制 思路:在事件拦截的地…...

RabbitMQ 发布确认机制

发布确认模式是避免消息由生产者到RabbitMQ消息丢失的一种手段 发布确认模式 原理说明实现方式开启confirm&#xff08;确认&#xff09;模式阻塞确认异步确认 总结 原理说明 生产者通过调用channel.confirmSelect方法将信道设置为confirm模式&#xff0c;之后RabbitMQ会返回Co…...

微信小程序使用rich-text解析富文本字符串的时候,遇到image标签图片很大超过屏幕

场景&#xff1a; 使用uniapp开发微信小程序&#xff0c;解析富文本文章需求 用到的组件&#xff1a; u-view2.0的u-parse uniapp提供的rich-text 以上两种组件都是解析富文本的作用&#xff0c;一般用于富文本解析场景&#xff0c;比如解析文章内容&#xff0c;商品详情&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参考文章 请求路径填写*&#xff0c;模块选择FastCgiModule&…...

sentinel核心流程源码解析

sentinel的处理槽(ProcessorSlot) 可以说&#xff0c;sentinel实现的各种功能就是由各处理槽完成的 ,ProcessorSlot定义了四个方法&#xff1a; 当进入该处理槽时触发该方法 处理完 entry方法之后触发该方法 退出该处理槽时触发该方法 exit方法处理完成时触发该方法 sentinel的…...

中睿天下Coremail | 2023年第二季度企业邮箱安全态势观察

今日&#xff0c;中睿天下联合Coremail邮件安全发布《2023第二季度企业邮箱安全性研究报告》&#xff0c;对2023第二季度和2023上半年的企业邮箱的安全风险进行了分析。 一 垃圾邮件同比下降16.38% 根据监测&#xff0c;2023年Q2垃圾邮件数量达到6.47亿封&#xff0c;环比下降…...

桶排序-1184:明明的随机数

【题目描述】 明明想在学校中请一些同学一起做一项问卷调查&#xff0c;为了实验的客观性&#xff0c;他先用计算机生成了N个1到1000之间的随机整数&#xff08;N≤100&#xff09;&#xff0c;对于其中重复的数字&#xff0c;只保留一个&#xff0c;把其余相同的数去掉&#x…...

Spring Boot中整合Keycloak OpenID Connect(OIDC)

在Spring Boot中整合Keycloak OpenID Connect&#xff08;OIDC&#xff09;是一个常见的任务&#xff0c;用于实现身份验证和授权。Keycloak是一个开源的身份和访问管理解决方案&#xff0c;而OpenID Connect是构建在OAuth 2.0之上的认证和授权协议。下面是一个简单的步骤指南&…...

如何使用Mac终端给树莓派pico构建C/C++程序进行开发,以及遇到各种问题该怎么处理,不使用任何IDE或编辑器(例如VS Code)

写本文的原因是官方的教程已经过时了&#xff0c;如果你现在按照官方教程来在 Mac 上进行配置&#xff0c;那么会遇到一堆问题&#xff0c;比如我几乎把能踩的“雷”都踩了。所以这里记录了完整过程&#xff0c;以及各种错误的原因和处理方法&#xff0c;不然以后换 Mac 了或者…...

linux 关机和重启

关机和重启 关机和重启之前最好先数据数据同步一下 # 将数据由内存同步到硬盘sync 关机 #shutdown [选项] 时间#立即进入维护模式shutdown now#立即重启shutdown -r now#20:00 重新启动计算机shutdown -r 20:00& #立即关机shutdown -h now# 20:00 关闭计算机shutdown -h 20…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...