【归并排序】| 详解归并排序核心代码之合并两个有序数组 力扣88
🎗️ 主页:小夜时雨
🎗️专栏:动态规划
🎗️如何活着,是我找寻的方向
目录
- 1. 题目解析
- 2. 代码
1. 题目解析
题目链接: https://leetcode.cn/problems/merge-sorted-array/description/
本道题是归并排序的核心代码区间, 所以还是十分重要的, 接下来我们来分析一下这道题目.
- 首先我们注意到这个是两个非递减的整数数组,那么很自然的一个想法就是从头开始遍历两个数组,谁小取出来排队即可。
- 取出来排队这个操作我们巨化为创建一个辅助数组,将数组中二者比较小的放入到这个辅助数组中, 直到遍历结束。
- 最后再将辅助数组拷贝到原始数组中即可。整体的思路还是比较符合实际我们进行比较排序的情况的。
具体实现过程:
- 创建一个 m + n 的辅助数组, 变量 cur1, cur2, i。
- cur1 遍历数组nums1, cur2遍历数组nums2,i 记录辅助数组填表的位置。
- cur1 和 cur2 while 循环同时遍历各自的数组, 比较二者的数,谁小放入到辅助数组中去,同时指针要向后移动一位。
- while(cur1 <= m - 1 && cur2 <= n - 1), 注意循环条件是并的关系, 所以当 while 循环跳出的时候, cur1 <= m - 1 或者 cur2 <= n - 1 有一个已经提前到数组的末尾了, 那还有另一个数组没有遍历完。
- 所以我们要接着遍历另外一个没有遍历完的,把数直接添加到辅助数组的后面(直接添加是因为这两个都是有序数组)
- 由于并不知道是哪一个指针先遍历完,所以要写两个判断。这里的判断我们继续用 while 循环继续代替。
- 遍历原数组把辅助数组中的数拷贝到原数组中即可。
2. 代码
看下面的代码对照着上面的流程解析会更加的清楚。
其实还有一种直接在原数组中进行拷贝的, 并不需要用到辅助数组,但是为了和后续归并排序联系在一起,我们此处只介绍了用辅助数组的具体过程,这个也更加容易理解(我们把不用辅助数组的代码也贴在最后面)。
// 这个就是归并排序的核心部分。 必须要会// 归并排序中用的就是这个思想。public void merge(int[] nums1, int m, int[] nums2, int n) {int[] tmp = new int[m + n];int cur1 = 0, cur2 = 0, i = 0;、// 合并两个有序数组到辅助数组中while(cur1 <= m - 1 && cur2 <= n - 1) tmp[i++] = nums1[cur1] <= nums2[cur2] ? nums1[cur1++] : nums2[cur2++];// 处理还没有遍历完的数组. 上面条件是并的关系,所以下面的while循环只会有一个执行while(cur1 <= m - 1) tmp[i++] = nums1[cur1++];while(cur2 <= n - 1) tmp[i++] = nums2[cur2++];// 遍历原数组, 还原辅助数组到原数组中for(int j = 0; j < m + n; j++) {nums1[j] = tmp[j];}return;}
不需要用到拷贝数组的写法代码(建议学会上面那一种写法,容易理解):
public void merge2(int[] nums1, int m, int[] nums2, int n) {//有一点利用归并排序的思想int i = m -1;int j = n -1; //分别记录有效数据的最后一位int k = m + n - 1; //记录nums1数组的最后一个位置// && 逻辑与 是为了保证索引不越界while(i >= 0 && j >= 0) {if (nums1[i] <= nums2[j]) {nums1[k] = nums2[j];k--;j--;}else {nums1[k] = nums1[i];k--;i--;}} // 走到这说明i 和 j有一个不为0,其中不用管数组1中的数据,因为要拷贝到数组1中,本身就是有序的。// 只需要判断 数组2的情况就行,把数组2中的数据拷贝到数组1中去 // 即是有可能数组1走完了,数组2中还有数据while(j >= 0) {nums1[k] = nums2[j];k--;j--;}}
🎗️🎗️🎗️ 好啦,到这里有关本题的分享就没了,如果感觉做的还不错的话可以点个赞,关注一下,你的支持就是我继续下去的动力,我们下期再见,拜了个拜~ ☆*: .。. o(≧▽≦)o .。.:*☆
相关文章:

【归并排序】| 详解归并排序核心代码之合并两个有序数组 力扣88
🎗️ 主页:小夜时雨 🎗️专栏:动态规划 🎗️如何活着,是我找寻的方向 目录 1. 题目解析2. 代码 1. 题目解析 题目链接: https://leetcode.cn/problems/merge-sorted-array/description/ 本道题是归并排序的…...

51单片机STC89C52RC——2.3 两个独立按键模拟控制LED流水灯方向
目的 按下K1键LED流水向左移动 按下K2键LED流水向右移动 一,STC单片机模块 二,独立按键 2.1 独立按键位置 2.2 独立按键电路图 这里要注意一个设计的bug P3_1 引脚对应是K1 P3_0 引脚对应是K2 要实现按一下点亮、再按一下熄灭,我们就需…...
Neo4j连接
终端输入: neo4j console 浏览器访问:http://localhost:7474/ 输入用户名和密码:neo4j, 梦想密码(首次neo4j) 代码连接用新的服务器地址: g Graph(neo4j://localhost:7687, auth(neo4j, ))…...

List 列表
文章目录 一、什么是 List 列表1.1 创建 List 列表的方式1.2 列表的新增函数方法1.3 列表的删除函数方法1.4 修改列表数据的方法1.5 列表的查询函数方法1.6 列表的排序和反序1.7 列表的复制 一、什么是 List 列表 List 列表:该数据类型定义的变量可以理解为是一个数…...

nginx ws长连接配置
nginx ws长连接配置 http根节点下配上 map $http_upgrade $connection_upgrade {default upgrade; close;}如下: server服务节点下,后端接口的代理配置 proxy_http_version 1.1;proxy_set_header Upgrade $http_upgrade;proxy_set_header Connec…...
Windows下访问wsl的数据
Windows下访问wsl的数据 有些人感受到的是雨,而很多人感受到的只有淋湿。 Windows下的wsl说实话还是挺不错的,对于开发而言,效果相当的可以。 比如在某个文件夹,Windows编辑好代码后,直接右键打开wsl,就可…...

机器学习笔记 - 用于3D数据分类、分割的Point Net简述
一、简述 在本文中,我们将了解Point Net,目前,处理图像数据的方法有很多。从传统的计算机视觉方法到使用卷积神经网络到Transformer方法,几乎任何 2D 图像应用都会有某种现有的方法。然而,当涉及到 3D 数据时,现成的工具和方法并不那么丰富。3D 空间中一个工具就是Point …...

vscode 连接 GitHub
目录 vscode连接github一、解决 github 登录问题二、通过 SSH 连接 github1、只有一个 git 账号2、切换 git 账号3、在两个账号之间切换 vscode 连接 gitee一、通过 HTTPS 连接二、通过 SSH 连接 vscode连接github 在 vscode 中首次使用 git push 命令时会要求输入 github 账户…...

集合java
1.集合 ArrayList 集合和数组的优势对比: 长度可变 添加数据的时候不需要考虑索引,默认将数据添加到末尾 package com.itheima;import java.util.ArrayList;/*public boolean add(要添加的元素) | 将指定的元素追加到此集合的末尾 | | p…...

智能体(Agent)实战——从gpts到auto gen
一.GPTs 智能体以大模型作为大脑,同时配备技能,使其能够完成具体的任务。同时,为了应用于垂直领域,我们需要为大模型定义一个角色,并构建知识库。最后,定义完整的流程,使其完成整个任务。以组会…...

PyTorch 张量数据类型
【数据类型】Python 与 PyTorch 常见数据类型对应: 用 a.type() 获取数据类型,用 isinstance(a, 目标类型) 进行类型合法化检测 >>> import torch >>> a torch.randn(2,3) >>> a tensor([[-1.7818, -0.2472, -2.0684],[ 0.…...

奇思妙想-可以通过图片闻见味道的设计
奇思妙想-可以通过图片闻见味道的设计 偷闲半日享清闲,炭火烧烤乐无边。肉串飘香引客至,笑语欢声绕云间。人生难得几回醉,且把烦恼抛九天。今宵共饮开怀酒,改日再战新篇章。周四的傍晚,难得的闲暇时光让我与几位挚友相…...
装饰者模式(设计模式)
装饰模式就是对一个类进行装饰,增强其方法行为,在装饰模式中,作为原来的这个类使用者还不应该感受到装饰前与装饰后有什么不同,否则就破坏了原有类的结构了,所以装饰器模式要做到对被装饰类的使用者透明,这…...
ADB调试命令大全
目录 前言命令大全1.显示当前运行的全部模拟器:adb devices2.启动ADB: adb start-server3.停止ADB: adb kill-server4.安装应用程序: adb install -r [apk文件]5.卸载应用程序: adb uninstall [packagename]6.将手机设备中的文件copy到本地计…...

查看npm版本异常,更新nvm版本解决问题
首先说说遇见的问题,基本上把nvm,npm的坑都排了一遍 nvm版本导致npm install报错 Unexpected token ‘.‘install和查看node版本都正确,结果查看npm版本时候报错 首先就是降低node版本… 可以说基本没用,如果要降低版本的话&…...
计算机行业
计算机行业环境分析 2022.01.12 计算机行业环境分析 计算机专业就业前景 随着科技的进步和信息事业的发展,尤其是计算机技术的发展与网络应用的逐渐普及。计算机已成为人们工作和生活中不可缺少的东西。IT行业迅猛发展,就业工作岗位也比比皆是。在最近…...

各种机器学习算法的应用场景分别是什么(比如朴素贝叶斯、决策树、K 近邻、SVM、逻辑回归最大熵模型)?
2023简直被人工智能相关话题席卷的一年。关于机器学习算法的热度,也再次飙升,网络上一些分享已经比较老了。那么今天借着查询和学习的机会,我也来浅浅分享下目前各种机器学习算法及其应用场景。 为了方便非专业的朋友阅读,我会从算…...
SQLite JDBC驱动程序
SQLite JDBC驱动程序下载地址: 下载地址...

Postgre 调优工具pgBadger部署
一,简介: pgBadger(日志分析器)类似于oracle的AWR报告(基于1小时,一天,一周,一月的报告),以图形化的方式帮助DBA更方便的找到隐含问题。 pgbadger是为了提高…...

【云原生】Kubernetes----Helm包管理器
目录 引言 一、Helm概述 1.Helm价值概述 2.Helm的基本概念 3.Helm名词介绍 二、安装Helm 1.下载二进制包 2.部署Helm环境 3.添加补全信息 三、使用Helm部署服务 1.创建chart 2.查看文件信息 3.安装chart 4.卸载chart 5.自定义chart服务部署 6.版本升级 7.版本…...

地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...