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

【数据结构OJ题】合并两个有序数组

原题链接:https://leetcode.cn/problems/merge-sorted-array/

目录

1. 题目描述

2. 思路分析

3. 代码实现


1. 题目描述

2. 思路分析

看到这道题,我们注意到nums1[ ]和nums2[ ]两个数组都是非递减的。所以我们很容易想到额外开一个数组tmp[ ],依次比较两个数组的元素,每次取小的尾插到新数组tmp[ ]即可。但是这需要额外再开空间。

 

 

 

也有一种方法是将这两个数组的元素都拷贝到一起,然后使用qsort排序  复杂度为O(NlogN)。

显然这两种方法的复杂度都不够优秀,是否有更好的方法呢?

我们可以倒着比较,取大的依次往前插入。等到有一个数组被遍历完,就结束。

因为两个数组都是非递减的,nums1[ ]数组的长度比nums2[ ]大,所以如果nums1[ ]先被遍历完,就将nums2[ ]没有被遍历的元素直接拷贝到nums1[ ]前面。

如果nums2[ ]先被遍历完,则不用额外操作(因为nums1[ ]整体本身就是非递减的,所以那些没有被遍历到的元素也是按非递减排列的)。

流程演示:

 ​​​​​​​

 

 

3. 代码实现

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int end1 = m - 1, end2 = n - 1, end = m + n - 1;while (end1 >= 0 && end2 >= 0){if (nums1[end1] >= nums2[end2])nums1[end--] = nums1[end1--];elsenums1[end--] = nums2[end2--];}while (end2 >= 0)nums1[end--] = nums2[end2--];
}

相关文章:

【数据结构OJ题】合并两个有序数组

原题链接:https://leetcode.cn/problems/merge-sorted-array/ 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析 看到这道题,我们注意到nums1[ ]和nums2[ ]两个数组都是非递减的。所以我们很容易想到额外开一个数组tmp[ ]&#x…...

数据结构笔记--归并排序及其拓展题(小和问题、逆序对问题)

目录 1--归并排序 2--小和问题 3--逆序对问题 1--归并排序 归并排序的核心思想&#xff1a;将一个无序的序列归并排序为一个有序的系列&#xff1b;通过递归将无序的序列二分&#xff0c;从底层开始将二分的序列归并排序为有序序列&#xff1b; #include <iostream> #…...

flutter开发实战-实现css线性渐变转换flutter渐变LinearGradient功能

flutter开发实战-实现css线性渐变转换flutter渐变LinearGradient功能 在之前项目开发中&#xff0c;遇到更换样式&#xff0c;由于从服务器端获取的样式均为css属性值&#xff0c;需要将其转换成flutter类对应的属性值。这里只处理线性渐变linear-gradient 比如渐变 “linear-…...

python推理小游戏bagels

python推理小游戏bagels bagels是一个推理小游戏&#xff0c;你的朋友想到一个随机的、没有重复的3位数字&#xff0c;你尝试去猜测它是什么。每次猜测之后&#xff0c;朋友就会给出3中类型的线索&#xff1a; Bagels: 你猜测的3个数都不在神秘数字中&#xff1b;Pico&#x…...

DBSCAN聚类

一、概述 DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种基于密度的聚类算法&#xff0c;簇集的划定完全由样本的聚集程度决定。聚集程度不足以构成簇落的那些样本视为噪声点&#xff0c;因此DBSCAN聚类的方式也可以用于异常点的检测。 二、算法…...

java+ssm美食推荐交流系统 7jsw7

随着社会的发展&#xff0c;美食推荐系统的管理形势越来越严峻。越来越多的用户利用互联网获得信息&#xff0c;但美食推荐信息鱼龙混杂&#xff0c;真假难以辨别。为了方便用户更好的获得美食推荐信息&#xff0c;因此&#xff0c;设计一款安全高效的美食推荐系统极为重要。 为…...

基于php雪花算法工具类Snowflake -来自chatGPT

<?phpclass Snowflake {// 定义Snowflake算法的各个参数private $workerIdBits 5;private $datacenterIdBits 5;private $sequenceBits 12;private $workerIdShift;private $datacenterIdShift;private $timestampLeftShift;private $maxWorkerId;private $maxDatacente…...

怎么加密文件夹才更安全?安全文件夹加密软件推荐

文件夹加密可以让其中数据更加安全&#xff0c;但并非所有加密方式都能够提高极高的安全强度。那么&#xff0c;怎么加密文件夹才更安全呢&#xff1f;下面我们就来了解一下那些安全的文件夹加密软件。 文件夹加密超级大师 如果要评选最安全的文件夹加密软件&#xff0c;那么文…...

知识分享和Tomcat简单部署press应用

一、简述静态网页和动态网页的区别。 静态网页: 静态网页是指运行于客户端的程序、网页、组件、纯粹HTML格式的网页; 如果有涉及网页内容的修改&#xff0c;就要修改源文件&#xff0c;重新上传到服务器。而且当网站信息量很大的时候&#xff0c;网页制作和维护都非常困…...

回归预测 | MATLAB实现SO-CNN-BiGRU蛇群算法优化卷积双向门控循环单元多输入单输出回归预测

回归预测 | MATLAB实现SO-CNN-BiGRU蛇群算法优化卷积双向门控循环单元多输入单输出回归预测 目录 回归预测 | MATLAB实现SO-CNN-BiGRU蛇群算法优化卷积双向门控循环单元多输入单输出回归预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 MATLAB实现SO-CNN-BiGRU蛇群算法…...

步入React前厅 - 组件和JSX

目录 扩展学习资料 购物车应用 编写React元素 /src/index.js 创建组件 /src/components/listItem.jsx /src/App.js 理解JSX【JavaScriptXML】 JSX是什么 JSX规则 /src/components/listItem.jsx 使用Fragments /src/App.js 为何要使用Fragments 表格中使用Fragme…...

SpringBoot整合Sfl4j+logback的实践

一、概述 对于一个web项目来说&#xff0c;日志框架是必不可少的&#xff0c;日志的记录可以帮助我们在开发以及维护过程中快速的定位错误。slf4j,log4j,logback,JDK Logging等这些日志框架都是我们常见的日志框架&#xff0c;本文主要介绍这些常见的日志框架关系和SpringBoot…...

IT 基础架构自动化

什么是 IT 基础架构自动化 IT 基础架构自动化是通过使用技术来控制和管理构成 IT 基础架构的软件、硬件、存储和其他网络组件来减少人为干预的过程&#xff0c;目标是构建高效、可靠的 IT 环境。 为什么要自动化 IT 基础架构 为客户和员工提供无缝的数字体验已成为企业的当务…...

Docker入门——保姆级

Docker概述 ​ —— Notes from WAX through KuangShen 准确来说&#xff0c;这是一篇学习笔记&#xff01;&#xff01;&#xff01; Docker为什么出现 一款产品&#xff1a;开发—上线 两套环境&#xff01;应用环境如何铜鼓&#xff1f; 开发 – 运维。避免“在我的电脑…...

MONGODB ---- Austindatabases 历年文章合集

开头还是介绍一下群&#xff0c;如果感兴趣polardb ,mongodb ,mysql ,postgresql ,redis 等有问题&#xff0c;有需求都可以加群群内有各大数据库行业大咖&#xff0c;CTO&#xff0c;可以解决你的问题。加群请联系 liuaustin3 &#xff0c;在新加的朋友会分到2群&#xff08;共…...

菠萝头 pinia和vuex对比 pinia比vuex更香 Pinia数据持久化及数据加密

前言 毕竟尤大佬都推荐使用pinia&#xff0c;支持vue2和vue3&#xff01; 如果熟悉vuex&#xff0c;花个把小时把pinia看一下&#xff0c;就不想用vuex了 支持选项式api和组合式api写法pinia没有mutations&#xff0c;只有&#xff1a;state、getters、actionspinia分模块不…...

机器学习笔记 - 关于GPT-4的一些问题清单

一、简述 据报道,GPT-4 的系统由八个模型组成,每个模型都有 2200 亿个参数。GPT-4 的参数总数估计约为 1.76 万亿个。 近年来,得益于 GPT-4 等高级语言模型的发展,自然语言处理(NLP) 取得了长足的进步。凭借其前所未有的规模和能力,GPT-4为语言 AI​​设立了新标准,并为机…...

sql 参数自动替换

需求&#xff1a;看日志时&#xff0c;有的sql 非常的长&#xff0c;参数比较多&#xff0c;无法直接在sql 客户端工具执行&#xff0c;如果一个一个的把问号占位符替换为参数太麻烦&#xff0c;因此写个html 小工具&#xff0c;批量替换&#xff1a; 代码&#xff1a; <!…...

Linux——设备树

目录 一、Linux 设备树的由来 二、Linux设备树的目的 1.平台识别 2.实时配置 3.设备植入 三、Linux 设备树的使用 1.基本数据格式 2.设备树实例解析 四、使用设备树的LED 驱动 五、习题 一、Linux 设备树的由来 在 Linux 内核源码的ARM 体系结构引入设备树之前&#x…...

网络:从socket编程的角度说明UDP和TCP的关系,http和tcp的区别

尝试从编程的角度解释各种网络协议。 UDP和TCP的关系 从Python的socket编程角度出发&#xff0c;UDP&#xff08;User Datagram Protocol&#xff09;和TCP&#xff08;Transmission Control Protocol&#xff09;是两种不同的传输协议。 TCP是一种面向连接的协议&#xff0c…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

网站指纹识别

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

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

k8s从入门到放弃之HPA控制器

k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率&#xff08;或其他自定义指标&#xff09;来调整这些对象的规模&#xff0c;从而帮助应用程序在负…...

在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南

在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南 背景介绍完整操作步骤1. 创建Docker容器环境2. 验证GUI显示功能3. 安装ROS Noetic4. 配置环境变量5. 创建ROS节点(小球运动模拟)6. 配置RVIZ默认视图7. 创建启动脚本8. 运行可视化系统效果展示与交互技术解析ROS节点通…...

欢乐熊大话蓝牙知识17:多连接 BLE 怎么设计服务不会乱?分层思维来救场!

多连接 BLE 怎么设计服务不会乱&#xff1f;分层思维来救场&#xff01; 作者按&#xff1a; 你是不是也遇到过 BLE 多连接时&#xff0c;调试现场像网吧“掉线风暴”&#xff1f; 温度传感器连上了&#xff0c;心率带丢了&#xff1b;一边 OTA 更新&#xff0c;一边通知卡壳。…...