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 + nnums2.length == n0 <= m, n <= 2001 <= 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合并两个有序数组
题目: 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终&…...
Ceph入门到精通-Nginx 大量请求 延迟优化
优化nginx以处理大量请求并减少延迟可以通过以下几种方法实现: 调整worker_processes和worker_connections参数:增加worker_processes值可以增加nginx的进程数量,提高并发处理能力。增加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,前者是框架,类似与MFC,而后者是QT的编译器,也可以使用Visual studio编辑,编译需要其他的 Index of /new_archive/qt/5.8/5.8.0...
AIGC+思维导图:提升你的学习与工作效率的「神器」
目录 一、产品简介 二、功能介绍 2.1 AI一句话生成思维导图 2.2百万模版免费用 2.3分屏视图,一屏读写 2.4团队空间,多人协作 2.5 云端跨平台化 2.6 免费够用,会员功能更强大 2.7 支持多种格式的导入导出 三、使用教程 3.1 使用AI…...
javaScript:DOM元素的获取(静态/动态获取)
目录 一.dom元素获取的意义与使用场景 使用场景(绝大多数js操作都需要dom操作) 总结/疑问解答! 二.DOM元素获取的常用方法(重点) 获取dom元素(动态) document.gerElementbyId() docume…...
数据结构前言
一、什么是数据结构? 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 上面是百度百科的定义,通俗的来讲数据结构就是数据元素集合与数据元素集合或者数据元素与数据元素之间的组成形式。 举个…...
Docker基于alpine带glibc的小型容器image
由于程序是C写的,gc编译,找了几个容器,生成比较小的是debianslim和ubuntu,生成后的大小分别为88MB,和91MB,还是太大了,于是想起一些小型容器如busybox或者alpine自己装glibc,但是试了…...
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如何有效对接网络安全需求
信息安全是一个防护市场。如果数字化程度低,数据量不够,对外接口少,攻击成本高,所获利益少,自然就没有什么攻击,车厂因此也不需要在防护上花费太多成本。所以此前尽管说得热闹,但并没有太多真实…...
hiveserver2经常挂断的原因
hiveserver2经常挂断的原因 HiveServer2 经常挂断可能有多种原因,以下是一些可能导致挂断的常见原因: 资源不足:HiveServer2 需要足够的内存和 CPU 资源来处理查询请求。如果资源不足,可能会导致 HiveServer2 挂断。请确保在配置…...
openeuler 23.03 安装mysql 8.X
遇到一堆问题:直接从mysql官下载,都不行。下列是失败的: 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下载应该靠谱:ht…...
网络安全—0基础学习笔记(黑客)
一、前言 1.这是一条坚持的道路,三分钟的热情可以放弃往下看了. 2.多练多想,不要离开了教程什么都不会了.最好看完教程自己独立完成技术方面的开发. 3.有时多 google,baidu,我们往往都遇不到好心的大神,谁会无聊天天给你做解答. 4.遇到实在搞不懂的,可以先放放,以后再来解决. …...
react HashRouter 与 BrowserRouter 的区别及使用场景
一、简介 在单页面应用中,如何在切换页面后,不刷新浏览器呢?为了解决这个问题,有两种方法,就是hash路由模式、history路由模式,而 react router 的两种路由就是使用这两种路由模式。 二、区别 HashRouter…...
痞子衡嵌入式:恩智浦i.MX RT1xxx系列MCU硬件那些事(2.3)- 串行NOR Flash下载算法(J-Link工具篇)
https://www.cnblogs.com/henjay724/p/13770137.html 大家好,我是痞子衡,是正经搞技术的痞子。今天痞子衡给大家介绍的是J-Link工具下i.MXRT的串行NOR Flash下载算法设计。 在i.MXRT硬件那些事系列之《在串行NOR Flash XIP调试原理》一文中,痞…...
多目标应用:基于多目标向日葵优化算法(MOSFO)的微电网多目标优化调度MATLAB
一、微网系统运行优化模型 参考文献: [1]李兴莘,张靖,何宇,等.基于改进粒子群算法的微电网多目标优化调度[J].电力科学与工程, 2021, 37(3):7 二、多目标向日葵优化算法 多目标向日葵优化算法(Multi-objective sunflower optimization,MOS…...
智能安全科技,Vatee万腾为您服务
在智能科技的引领下,Vatee万腾将为您点亮投资之路,助您在金融市场中抓住机遇,实现财务目标。作为一家融合科技与投资的先锋平台,Vatee万腾致力于为投资者提供智能化的投资方案和支持。 Vatee万腾以其先进的智能科技为基础…...
Scala中的类型检查和转换,以及泛型,scala泛型的协变和逆变
Scala中的类型检查和转换,以及泛型 类型检查和转换 说明 (1) obj.isInstanceOf[T]:判断 obj 是不是T 类型。 (2) obj.asInstanceOf[T]:将 obj 强转成 T 类型。 (3) cla…...
【数据结构】C语言队列(详解)
前言: 💥🎈个人主页:Dream_Chaser~ 🎈💥 ✨✨专栏:http://t.csdn.cn/oXkBa ⛳⛳本篇内容:c语言数据结构--C语言实现队列 目录 一.队列概念及结构 1.1队列的概念 1.2队列的结构 二.队列的实现 2.1头文…...
【数据结构初阶】一. 复杂度讲解
相关代码gitee自取: C语言学习日记: 加油努力 (gitee.com) 接上期: 学C的第三十四天【程序环境和预处理】_高高的胖子的博客-CSDN博客 1 . 算法效率 (1). 什么是数据结构: 数据结构(Data Structure)是计算机存储、…...
Python实战:基于余弦相似度的中文短文本相似性计算
1. 为什么需要中文短文本相似性计算? 在日常工作和生活中,我们经常会遇到需要比较两段中文文本相似度的场景。比如在客服系统中自动匹配相似问题,在内容平台上检测重复文章,或者在搜索引擎中推荐相关文档。这些场景都离不开文本相…...
杰理之通话之后siri就会异常,siri出来的非常慢【篇】
在连接蓝牙上没有通话前耳机按键打开siri是正常的...
Ostrakon-VL-8B赋能微信小程序:开发餐饮AI点餐助手
Ostrakon-VL-8B赋能微信小程序:开发餐饮AI点餐助手 你有没有过这样的经历?走进一家新餐厅,面对琳琅满目的菜单,却不知道哪道菜合自己口味,或者担心食材里有自己过敏的东西。又或者,正在控制饮食的你&#…...
5W功耗实现25TOPS算力,LM2-100-V0算力模组破解AI安防核心难题
在智慧安防边缘AI应用快速部署需求的背景下,设备制造商常面临终端设备算力不足、功耗超标、体积受限、部署太慢等困境。模型越复杂,终端越吃力;设备要小型化,算力要打折扣;长期稳定运行,散热与功耗又成瓶颈…...
【单片机】STM32晶振引脚不连晶振时的做法
STM32不使用外部晶振时,OSC_IN和 OSC_OUT接法:1、对于100脚或者144脚的产品,OSC_IN应接地,OSC_OUT应悬空;2、对于少于100脚的产品,有两种接法:OSC_IN和OSC_OUT分别通过10K电阻接地,此方法可提高…...
实战演练:基于快马平台生成电商全流程自动化测试并与Jenkins集成
今天想和大家分享一个最近用InsCode(快马)平台完成的电商自动化测试实战项目。这个项目模拟了真实电商平台的核心业务流程,从用户注册登录到完成支付的全流程测试,特别适合需要快速搭建自动化测试体系的小伙伴参考。 项目背景与设计思路 电商系统的稳定…...
突破网盘下载瓶颈:开源工具如何重塑你的文件获取体验
突破网盘下载瓶颈:开源工具如何重塑你的文件获取体验 【免费下载链接】Online-disk-direct-link-download-assistant 一个基于 JavaScript 的网盘文件下载地址获取工具。基于【网盘直链下载助手】修改 ,支持 百度网盘 / 阿里云盘 / 中国移动云盘 / 天翼云…...
人形机器人手指关节选材:铝合金 vs PEEK,谁才是轻量化的终极方案?
在人形机器人研发中,末端执行器(手部)的性能直接决定了机器人的交互上限。而在手指关节这种“空间极度受限、重量极度敏感、运动频率极高”的部位,选铝合金还是 PEEK(聚醚醚酮),本质上是在“结构…...
多维创新打造强泛化智能体模型,LongCat-Flash-Thinking-2601技术报告
在技术领域,我们常常被那些闪耀的、可见的成果所吸引。今天,这个焦点无疑是大语言模型技术。它们的流畅对话、惊人的创造力,让我们得以一窥未来的轮廓。然而,作为在企业一线构建、部署和维护复杂系统的实践者,我们深知…...
零基础入门飞书机器人开发:快马平台带你写好第一个openclaw程序
零基础入门飞书机器人开发:快马平台带你写好第一个openclaw程序 最近想给团队做个飞书机器人小助手,但作为编程新手完全不知道从哪开始。摸索后发现用openclaw框架配合InsCode(快马)平台特别适合零基础入门,这里记录下我的学习过程。 1. 理…...
