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)是计算机存储、…...
如何用MiniAGI进行技术分析:比特币价格预测实战指南
如何用MiniAGI进行技术分析:比特币价格预测实战指南 【免费下载链接】mini-agi MiniAGI is a minimal general-purpose autonomous agent based on GPT-3.5 / GPT-4. Can analyze stock prices, perform network security tests, create art, and order pizza. 项…...
用JavaScript高效生成专业PPT:PptxGenJS深度解析与5种实战应用
用JavaScript高效生成专业PPT:PptxGenJS深度解析与5种实战应用 【免费下载链接】PptxGenJS Build PowerPoint presentations with JavaScript. Works with Node, React, web browsers, and more. 项目地址: https://gitcode.com/gh_mirrors/pp/PptxGenJS 在数…...
避坑指南:海康摄像头与Livox雷达时间同步失败的5个常见原因及解决方案
海康摄像头与Livox雷达时间同步实战:从原理到排错的完整指南 当海康工业摄像头遇上Livox Mid-360激光雷达,时间同步问题就像两个说着不同方言的专家试图合作——看似简单,实则暗藏玄机。作为在工业视觉与三维感知融合领域摸爬滚打多年的工程师…...
技术深度解析:如何通过Turbo Boost动态控制优化Mac系统性能与散热管理
技术深度解析:如何通过Turbo Boost动态控制优化Mac系统性能与散热管理 【免费下载链接】Turbo-Boost-Switcher Turbo Boost disabler / enable app for Mac OS X 项目地址: https://gitcode.com/gh_mirrors/tu/Turbo-Boost-Switcher Turbo Boost Switcher是一…...
GCP 项目 IAM 与结算账号管理指南
5 分钟速览 快速完成 GCP 项目的用户权限和结算管理。 我想… 操作 给用户添加项目结算管理权限 IAM → Grant Access → 分配 Viewer + Project Billing Manager 查看谁有结算权限 IAM → 筛选 Billing 相关角色 修改项目关联的结算账号 Billing → Account Management → Cha…...
像素语言·维度裂变器:5分钟上手,像玩游戏一样改写你的文字
像素语言维度裂变器:5分钟上手,像玩游戏一样改写你的文字 1. 认识你的文字冒险工坊 像素语言维度裂变器是一款将AI文本改写变成像素冒险游戏的创意工具。它基于MT5-Zero-Shot-Augment引擎,但完全颠覆了传统AI工具的刻板印象,把枯…...
STM32+LWIP实战:ETH外设配置避坑指南(基于HAL库)
STM32LWIP实战:ETH外设配置避坑指南(基于HAL库) 第一次在STM32上移植LWIP协议栈时,我盯着PHY芯片的Link灯整整三天没亮。直到发现CubeMX生成的代码里漏了一个关键寄存器配置——这个教训让我意识到,ETH外设的配置远不是…...
实战esp32智能门禁系统,快马平台生成完整应用代码助力项目落地
最近在做一个办公室智能门禁的小项目,用ESP32实现了完整的门禁控制功能。整个过程挺有意思的,特别是发现用InsCode(快马)平台可以快速生成项目代码框架,省去了很多重复工作。下面分享下具体实现思路和经验。 硬件选型与连接 ESP32作为主控板性…...
为什么你的经典游戏在Windows 10/11上无法运行?DDrawCompat完美解决方案
为什么你的经典游戏在Windows 10/11上无法运行?DDrawCompat完美解决方案 【免费下载链接】DDrawCompat DirectDraw and Direct3D 1-7 compatibility, performance and visual enhancements for Windows Vista, 7, 8, 10 and 11 项目地址: https://gitcode.com/gh_…...
BilibiliDown:三步实现B站音频高效提取与批量处理全攻略
BilibiliDown:三步实现B站音频高效提取与批量处理全攻略 【免费下载链接】BilibiliDown (GUI-多平台支持) B站 哔哩哔哩 视频下载器。支持稍后再看、收藏夹、UP主视频批量下载|Bilibili Video Downloader 😳 项目地址: https://gitcode.com/gh_mirrors…...
