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

leetcode88合并两个有序数组

题目:

给你两个按 非递减顺序 排列的整数数组 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

解决:

解法1:利用Arrays中的sort方法排序直接求解

public void merge(int[] nums1,int m,int[] nums2,int n) {for(int i=0;i<n;i++){nums1[m+i]=nums2[i];}Arrays.sort(nums1);}

快速排序,时间复杂度为O((m+n)log(m+n))。代码效率不是特别高。其最大的问题是,题目给的数组元素本来是有序的,但这样混起来之后用sort排序相当于又重新排序了一遍,即没有充分利用元素的有序性。


解法2:用双指针

每次从两个数组的头部各取出一个数比较,把比较小的结果复制到临时数组中,再把比较小数所在数组指针后移一位。把两个数组元素都复制到临时数组后,临时数组的结果就是排序以后的结果了。再把临时数组的元素复制到nums1。这样的话两个数组都只循环了一遍,时间复杂度为O(m+n)。空间复杂度也是O(m+n)。

public void merge(int[] nums1,int m,int[] nums2,int n) {int k=m+n;int[] temp=new int[k];for(int index=0,nums1Index=0,nums2Index=0;index<k;index++){if(nums1Index>=m) {//nums1数组已经取完,接下来完全取nums2数组的值temp[index]=nums2[nums2Index++];}else if(nums2Index>=n){temp[index]=nums1[nums1Index++];}else if(nums1[nums1Index]<nums2[nums2Index]){//nums1数组元素值小于nums2数组元素值,取nums1数组的值temp[index]=nums1[nums1Index++];}else{temp[index]=nums2[nums2Index++];}}for(int i=0;i<k;i++){nums1[i]=temp[i];}}

解法3:用双指针,倒序处理

把nums2的最后一个元素与nums1的有效的最后一个元素比较,把大的放在nums1的最后一个0的位置。再把刚才的指针往前移一位,再比较这样就用到nums1的空间了,不用引入临时数组。这样时间复杂度为O(m+n),空间复杂度为O(m)。

    public void merge(int[] nums1,int m,int[] nums2,int n) {int k=m+n;for(int index=k-1,nums1Index=m-1,nums2Index=n-1;index>=0;index--){if(nums1Index<0) {//nums1数组已经取完,接下来完全取nums2数组的值nums1[index]=nums2[nums2Index--];}else if(nums2Index<0){break;}else if(nums1[nums1Index]>nums2[nums2Index]){//nums1数组元素值大于nums2数组元素值,取nums1数组的值nums1[index]=nums1[nums1Index--];}else{nums1[index]=nums2[nums2Index--];}}}

加油加油^_^

相关文章:

leetcode88合并两个有序数组

题目&#xff1a; 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2&#xff0c;另有两个整数 m 和 n &#xff0c;分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中&#xff0c;使合并后的数组同样按 非递减顺序 排列。 注意&#xff1a;最终&…...

Ceph入门到精通-Nginx 大量请求 延迟优化

优化nginx以处理大量请求并减少延迟可以通过以下几种方法实现&#xff1a; 调整worker_processes和worker_connections参数&#xff1a;增加worker_processes值可以增加nginx的进程数量&#xff0c;提高并发处理能力。增加worker_connections参数的值可以增加每个worker进程可…...

Vulnstack----5、ATTCK红队评估实战靶场五

文章目录 一 环境搭建二 外网渗透三 内网信息收集3.1 本机信息收集3.2 域内信息收集 四 横向移动4.1 路由转发和代理通道4.2 抓取域用户密码4.3 使用Psexec登录域控4.4 3389远程登录 五、痕迹清理 一 环境搭建 1、项目地址 http://vulnstack.qiyuanxuetang.net/vuln/detail/7/ …...

QT 5.8

QT与Qt Creator&#xff0c;前者是框架&#xff0c;类似与MFC&#xff0c;而后者是QT的编译器&#xff0c;也可以使用Visual studio编辑&#xff0c;编译需要其他的 Index of /new_archive/qt/5.8/5.8.0...

AIGC+思维导图:提升你的学习与工作效率的「神器」

目录 一、产品简介 二、功能介绍 2.1 AI一句话生成思维导图 2.2百万模版免费用 2.3分屏视图&#xff0c;一屏读写 2.4团队空间&#xff0c;多人协作 2.5 云端跨平台化 2.6 免费够用&#xff0c;会员功能更强大 2.7 支持多种格式的导入导出 三、使用教程 3.1 使用AI…...

javaScript:DOM元素的获取(静态/动态获取)

目录 一.dom元素获取的意义与使用场景 使用场景&#xff08;绝大多数js操作都需要dom操作&#xff09; 总结/疑问解答&#xff01; 二.DOM元素获取的常用方法&#xff08;重点&#xff09; 获取dom元素&#xff08;动态&#xff09; document.gerElementbyId() docume…...

数据结构前言

一、什么是数据结构&#xff1f; 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 上面是百度百科的定义&#xff0c;通俗的来讲数据结构就是数据元素集合与数据元素集合或者数据元素与数据元素之间的组成形式。 举个…...

Docker基于alpine带glibc的小型容器image

由于程序是C写的&#xff0c;gc编译&#xff0c;找了几个容器&#xff0c;生成比较小的是debianslim和ubuntu&#xff0c;生成后的大小分别为88MB&#xff0c;和91MB&#xff0c;还是太大了&#xff0c;于是想起一些小型容器如busybox或者alpine自己装glibc&#xff0c;但是试了…...

Nginx教程

Nginx教程 01-Nginx简介02-windows安装Nginx03-Nginx目录结构04-Linux安装Nginx05-linux下源码安装nginx06-linux下nginx配置07-在docker中安装nginx08-源码安装和yum安装的区别09-Nginx运行组和运行用户10-卸载nginx11-nginx的基本原理和架构12-nginx是如何处理请求的13-nginx…...

直播预约|哪吒汽车岳文强:OEM和Tier1如何有效对接网络安全需求

信息安全是一个防护市场。如果数字化程度低&#xff0c;数据量不够&#xff0c;对外接口少&#xff0c;攻击成本高&#xff0c;所获利益少&#xff0c;自然就没有什么攻击&#xff0c;车厂因此也不需要在防护上花费太多成本。所以此前尽管说得热闹&#xff0c;但并没有太多真实…...

hiveserver2经常挂断的原因

hiveserver2经常挂断的原因 HiveServer2 经常挂断可能有多种原因&#xff0c;以下是一些可能导致挂断的常见原因&#xff1a; 资源不足&#xff1a;HiveServer2 需要足够的内存和 CPU 资源来处理查询请求。如果资源不足&#xff0c;可能会导致 HiveServer2 挂断。请确保在配置…...

openeuler 23.03 安装mysql 8.X

遇到一堆问题&#xff1a;直接从mysql官下载&#xff0c;都不行。下列是失败的&#xff1a; mysql80-community-release-el8-1.noarch.rpm mysql-8.0.34-1.el8.x86_64.rpm-bundle.tar mysql-8.1.0-1.el9.x86_64.rpm-bundle.tar 后来想从openeuler下载应该靠谱&#xff1a;ht…...

网络安全—0基础学习笔记(黑客)

一、前言 1.这是一条坚持的道路,三分钟的热情可以放弃往下看了. 2.多练多想,不要离开了教程什么都不会了.最好看完教程自己独立完成技术方面的开发. 3.有时多 google,baidu,我们往往都遇不到好心的大神,谁会无聊天天给你做解答. 4.遇到实在搞不懂的,可以先放放,以后再来解决. …...

react HashRouter 与 BrowserRouter 的区别及使用场景

一、简介 在单页面应用中&#xff0c;如何在切换页面后&#xff0c;不刷新浏览器呢&#xff1f;为了解决这个问题&#xff0c;有两种方法&#xff0c;就是hash路由模式、history路由模式&#xff0c;而 react router 的两种路由就是使用这两种路由模式。 二、区别 HashRouter…...

痞子衡嵌入式:恩智浦i.MX RT1xxx系列MCU硬件那些事(2.3)- 串行NOR Flash下载算法(J-Link工具篇)

https://www.cnblogs.com/henjay724/p/13770137.html 大家好&#xff0c;我是痞子衡&#xff0c;是正经搞技术的痞子。今天痞子衡给大家介绍的是J-Link工具下i.MXRT的串行NOR Flash下载算法设计。 在i.MXRT硬件那些事系列之《在串行NOR Flash XIP调试原理》一文中&#xff0c;痞…...

多目标应用:基于多目标向日葵优化算法(MOSFO)的微电网多目标优化调度MATLAB

一、微网系统运行优化模型 参考文献&#xff1a; [1]李兴莘,张靖,何宇,等.基于改进粒子群算法的微电网多目标优化调度[J].电力科学与工程, 2021, 37(3):7 二、多目标向日葵优化算法 多目标向日葵优化算法&#xff08;Multi-objective sunflower optimization&#xff0c;MOS…...

智能安全科技,Vatee万腾为您服务

在智能科技的引领下&#xff0c;Vatee万腾将为您点亮投资之路&#xff0c;助您在金融市场中抓住机遇&#xff0c;实现财务目标。作为一家融合科技与投资的先锋平台&#xff0c;Vatee万腾致力于为投资者提供智能化的投资方案和支持。 Vatee万腾以其先进的智能科技为基础&#xf…...

Scala中的类型检查和转换,以及泛型,scala泛型的协变和逆变

Scala中的类型检查和转换&#xff0c;以及泛型 类型检查和转换 说明 &#xff08;1&#xff09; obj.isInstanceOf[T]&#xff1a;判断 obj 是不是T 类型。 &#xff08;2&#xff09; obj.asInstanceOf[T]&#xff1a;将 obj 强转成 T 类型。 &#xff08;3&#xff09; cla…...

【数据结构】C语言队列(详解)

前言: &#x1f4a5;&#x1f388;个人主页:​​​​​​Dream_Chaser&#xff5e; &#x1f388;&#x1f4a5; ✨✨专栏:http://t.csdn.cn/oXkBa ⛳⛳本篇内容:c语言数据结构--C语言实现队列 目录 一.队列概念及结构 1.1队列的概念 1.2队列的结构 二.队列的实现 2.1头文…...

【数据结构初阶】一. 复杂度讲解

相关代码gitee自取&#xff1a; C语言学习日记: 加油努力 (gitee.com) 接上期&#xff1a; 学C的第三十四天【程序环境和预处理】_高高的胖子的博客-CSDN博客 1 . 算法效率 &#xff08;1&#xff09;. 什么是数据结构&#xff1a; 数据结构(Data Structure)是计算机存储、…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...