有序数组合并php,让我们一起啃算法----合并两个有序数组

不念不忘少年蓝@ 2023-01-16 06:55 131阅读 0赞

合并两个有序数组(Merge-Sorted-Array)

题干：

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。

你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。

示例:

输入:

nums1 = \[1,2,3,0,0,0\], m = 3

nums2 = \[2,5,6\], n = 3

输出: \[1,2,2,3,5,6\]

来源：力扣(LeetCode)

这是一题关于数组的题目。目前为止讲解数组、字符串相关的题目都会引入一个解题思路： 双指针思路。其实就是想让小伙伴们培养一个习惯：面对数组、字符串类型的题目先用 双指针思路 来捣腾捣腾。

当然这题也是引用这个思路来解题，只不过这时候的 双指针 不在指向一个数组，而是分别指向数组 num1 和 num2。

解题思路

简单粗暴的方式就是将 num1 和 num2 直接合并，再重新排序，当然不建议这么做啦。

我们仔细审一下题：题目告诉我们 num1 和 num2 是有序的，并且是从小到大排序的。那我们是不是可以从左到右依次比较 num1 和 num2 中的元素值，并将 较小的值minV 逐一存储到一个新的数组 num3 中。

但是题目有一个限制：需要将 num2 直接合并到 num1 中。这时候我们发现用从左到右的方式遍历，并将 minV 插入到 num1 中势必会产生挪动 num1 元素的操作，例如：需要在 num1 索引为 2 的位置插入 minV，那么需要将原本 索引为 2 的元素以及之后的元素都向后挪一位，空出索引为 2 的位置。成本有点大，并且也不好实现。

那么如何解决上面的问题呢？其实换成从右向左遍历就行啦。我们知道 num1 现在的长度为 m，当前最大索引记为 i ， num2 的长度为 n，当前最大索引记为 j，合并之后 num1 的长度应该是 m + n，最大索引记为 max。我们比较 num1\[i\] 与 num2\[j\] 的大小，如果 num1\[i\] 大于 num2\[j\] ，那么 num1\[max\] = num1\[i\]，max 向左移动一位，i 向左移动一位，反之 num1\[max\] = num2\[j\]，max 向左移动一位，j 向左移动一位。重复上面的操作，具体流程以及一些边界问题，查看下面的流程图：

![1460000022603231][]

代码实现

func merge(nums1 \[\]int, m int, nums2 \[\]int, n int) \{

// max 指向 nums1 与 nums2 合并之后的最后一个元素

max := m + n - 1

// 指向 num1 最后一个元素

i := m - 1

// 指向 num2 最后一个元素

j := n -1

for i >= 0 && j >= 0 \{

// 从右向左比较值的大小

if nums1\[i\] > nums2\[j\] \{

nums1\[max\] = nums1\[i\]

// i 向左移动

i--

\} else \{

nums1\[max\] = nums2\[j\]

// j 向左移动

j--

\}

// max 向左移动

max --

\}

// 如果 i 越界了，将 nums2 剩余的元素赋值到 num1 的 \[0,m\] 之间

for j >= 0 \{

nums1\[max\] = nums2\[j\]

max--

j--

\}

// 如果 j 越界了，其实下面这个循环可以省略。

for i >= 0 \{

nums1\[max\] = nums1\[i\]

max--

i--

\}

\}

总结

有疑问加站长微信联系(非本文作者)

[1460000022603231]: /images/20221022/0c6855e0d3714319974230df9bbff491.png

发表评论取消回复

表情：

评论列表（有 0 条评论，131人围观）

还没有评论，来说两句吧...

相关阅读

相关合并两个有序数组

88. 合并两个有序数组 > 给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元

我就是我/ 2024年04月06日 10:21/ 0 赞/ 98 阅读

相关算法：合并两个有序整数数组

描述：有arr1，arr2两个已排序数组，设计算法，合并两个数组，并且合并后的数组仍是有序的不得使用已有的任何库函数或数据结构，只通过基本数组完成以下的结构是O（n

我就是我/ 2023年10月10日 09:54/ 0 赞/ 37 阅读

相关合并两个有序数组（PHP）

<?php //合并两个有序数组 function mergeArr($arr1, $arr2) { $p1 = c

逃离我推掉我的手/ 2023年02月23日 08:55/ 0 赞/ 10 阅读

相关有序数组合并php,让我们一起啃算法----合并两个有序数组

合并两个有序数组(Merge-Sorted-Array) 题干：给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums

不念不忘少年蓝@/ 2023年01月16日 06:55/ 0 赞/ 132 阅读

相关合并两个有序数组

合并两个有序数组 1、参考资料 https://leetcode-cn.com/problems/merge-sorted-array/ 2、题目要求 >

绝地灬酷狼/ 2022年12月08日 05:15/ 0 赞/ 242 阅读

相关两个有序数组合并成一个有序数组

两个有序数组合并成一个有序数组 1. 题目描述数组a是有序的，数组b也是有序的，如何高效地合并它们成一个数组，并且新数组也是有序的？ 2.

冷不防/ 2022年08月06日 02:11/ 0 赞/ 252 阅读

相关两个有序数组合并成一个有序数组

思想：先依次比较两个数组，按照小的就传入新的数组。当这次比较完之后可能有一个数组的长度很长，留下一些数组，然后在新数组的末尾插入即可。代码： pub

亦凉/ 2022年08月04日 08:39/ 0 赞/ 297 阅读

相关合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和 nums2 的

╰半夏微凉°/ 2022年04月16日 06:11/ 0 赞/ 310 阅读

相关合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和 nums2

一时失言乱红尘/ 2021年11月16日 12:52/ 0 赞/ 391 阅读

相关 88、合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明: 初始化 nums1 和 nums

﹏ヽ暗。殇╰゛Y/ 2021年11月01日 15:26/ 0 赞/ 455 阅读