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

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

算法笔记2

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

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

rknn toolkit2搭建和推理

安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 &#xff0c;不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源&#xff08;最常用&#xff09; conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...