【归并排序】| 详解归并排序核心代码之合并两个有序数组 力扣88

2024-06-16 19:20

本文主要是介绍【归并排序】| 详解归并排序核心代码之合并两个有序数组 力扣88,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

🎗️ 主页:小夜时雨
🎗️专栏:动态规划
🎗️如何活着,是我找寻的方向

优雅

目录

  • 1. 题目解析
  • 2. 代码

1. 题目解析

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

在这里插入图片描述

本道题是归并排序的核心代码区间, 所以还是十分重要的, 接下来我们来分析一下这道题目.

  • 首先我们注意到这个是两个非递减的整数数组,那么很自然的一个想法就是从头开始遍历两个数组,谁小取出来排队即可。
  • 取出来排队这个操作我们巨化为创建一个辅助数组,将数组中二者比较小的放入到这个辅助数组中, 直到遍历结束。
  • 最后再将辅助数组拷贝到原始数组中即可。整体的思路还是比较符合实际我们进行比较排序的情况的。

具体实现过程:

  1. 创建一个 m + n 的辅助数组, 变量 cur1, cur2, i。
  2. cur1 遍历数组nums1, cur2遍历数组nums2,i 记录辅助数组填表的位置。
  3. cur1 和 cur2 while 循环同时遍历各自的数组, 比较二者的数,谁小放入到辅助数组中去,同时指针要向后移动一位。
  4. while(cur1 <= m - 1 && cur2 <= n - 1), 注意循环条件是并的关系, 所以当 while 循环跳出的时候, cur1 <= m - 1 或者 cur2 <= n - 1 有一个已经提前到数组的末尾了, 那还有另一个数组没有遍历完。
  5. 所以我们要接着遍历另外一个没有遍历完的,把数直接添加到辅助数组的后面(直接添加是因为这两个都是有序数组)
  6. 由于并不知道是哪一个指针先遍历完,所以要写两个判断。这里的判断我们继续用 while 循环继续代替。
  7. 遍历原数组把辅助数组中的数拷贝到原数组中即可。

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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1067325

相关文章

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Redis Pipeline(管道) 详解

《RedisPipeline(管道)详解》Pipeline管道是Redis提供的一种批量执行命令的机制,通过将多个命令一次性发送到服务器并统一接收响应,减少网络往返次数(RTT),显著提升执行效率... 目录Redis Pipeline 详解1. Pipeline 的核心概念2. 工作原理与性能提升3. 核

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组