当前位置: 首页 > 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…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...