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

三斤和他的喵的个人博客 / 176 / 3 / 创建于 4年前 / 更新于 4年前

合并两个有序数组（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 向左移动一位。重复上面的操作，具体流程以及一些边界问题，查看下面的流程图：

代码实现

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--
    }
}

总结

每天进步一点点，加油！
算法教程项目，每天更新一题，点个 star 支持一下呀：
github.com/wx-satellite/learning-a...

算法数据结构 leetcode

本作品采用《CC 协议》，转载必须注明作者和本文链接

三斤

三斤和他的喵

课程读者 172 声望

一个PHPer的修行之路。欢迎大家关注我的公众号《三斤和他的喵》

2 人点赞

我们将带你从零开发一个项目并部署到线上，本课程教授 Web 开发中专业、实用的技能，如 Git 工作流、Laravel Mix 前端工作流等。

从零开发一个电商项目，功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等

推荐文章：

更多推荐...

面试 POPER 的后端开发工程师的离奇经历 35 / 104 |

分享创造

📙《高并发的哲学原理》开源图书发布十一天 star 数已经破千！ 47 / 16 |

博客

PHP面试高薪宝典系列: 常见基础算法（附完整代码） 23 / 3 |

博客

强一致性的分布式事务几种模式对比（php有了新方案） 33 / 20 |

博客

PHP实现汉诺塔算法 21 / 9 |

博客

PHP使用动态规划实现最优红包组合 33 / 5 |

讨论数量: 3

yzh52521

33 声望

function merge(&$nums1, $m, $nums2, $n) {
       array_splice($nums1, $m);
        $nums1 = array_merge($nums1, $nums2);
        sort($nums1);
        return $nums1;
    }

4年前评论

三斤和他的喵（楼主）

是个狠人 :wave:

captain2021

哈哈哈，大力出奇迹

captain2021

Laravel 5.8 译者 422 声望 / 开发 @ 谈笑风生

function merge($nums1, $m, $nums2, $n) {
    $i = $m - 1;
    $j = $n - 1;
    $max = $m + $n - 1;

    while ($i >= 0 && $j >= 0) {
        if ($nums1[$i] > $nums2[$j]) {
            $nums1[$max] = $nums1[$i];
            $i--;
        } else {
            $nums1[$max] = $nums2[$j];
            $j--;
        }

        $max--;
    }

    while ($j >= 0) {
        $nums1[$max] = $nums2[$j];
        $j--;
        $max--;
    }

    return $nums1;
}

return merge([1,2,3,0,0,0], 3, [2,5,6], 3);

4年前评论

captain2021 （作者）

这段代码在LeetCode执行返回不正确的结果，在php7.4就可以，有大佬看看是什么原因导致的吗？

取名字好烦。

0 声望

有点东西

3年前评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

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

合并两个有序数组（Merge-Sorted-Array）

解题思路

代码实现

总结

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

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

合并两个有序数组（Merge-Sorted-Array）

解题思路

代码实现

总结

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录