一起养成写作习惯！这是我参与「掘金日新计划 · 4 月更文挑战」的第14天，点击查看活动详情。

【刷题日记】88. 合并两个有序数组

本次刷题日记的第 34 篇，力扣题为：88. 合并两个有序数组 ，简单

一、题目描述：

今天来刷一个数组的题目，据说数组和字符串的题目，考查的情况是最多的，莫非是因为代码量比较小？

来咱们仔细看这道数组题目，一起来分析分析

二、这道题考察了什么思想？你的思路是什么？

合并数组题目，到底给了我们那些重要信息呢？

• 题目中会给出 2 个数组，nums1 的数组长度是 m+n，且 nums1 的后 n 位数都是 0
• 给出的 2 个数组，都是递增的数组，题目要求我们合并后的结果放在 nums1 中，也需要是递增的

看到这个题目，比较好思考的其实是，咱们直接将 nums2 中的数字，一个一个的插入到 nums 1 中，类似于这样的情况：

但是上述这种方式会根据不同的实例，时间复杂度也是不确定的，例如咱么用 nums2 中的 数字 2 插入到 nums1 中的时候

咱们就需要将 nums1 原有位置上的  3 向后移动1位，如果咱们是替换或者插入到 nums 1 数组头上，那么需要向后偏移的数字则会更多， 这种方式不太靠谱

我们得换一个思维瞅瞅

例如我们可以尝试这种方式：

咱们可以创建一个帮助的数组，长度是 m+n，也就是说和 nums1 的长度保持一致，咱们比较 num1 和 nums2 的每一个数字，数字小的就加入到 帮助数组中

这样子做就比较纯粹，也比较好思考，有点大道至简的意思吧

那咱们就开始实现脑海里面的思维了

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码，这里需要注意在我们遍历完 nums1 或者 nums2 的有序数字之后的逻辑处理和拼接处理

编码如下：

func merge(nums1 []int, m int, nums2 []int, n int) {
    // 创建一个帮助的数组
    helper := make([]int, 0, m+n)
    i, j := 0, 0
    for {
        // 如果 nums1 前面的有序数字都比较完了，那么剩下的数字中，就将 nums2 剩下的数字全部拼过来
        if i == m {
            helper = append(helper, nums2[j:]...)
            break
        }
        // 道理同上
        if j == n {
            helper = append(helper, nums1[i:]...)
            break
        }
        // nums1 和 nums2 比较，将小的数加入结果集
        if nums1[i] < nums2[j] {
            helper = append(helper, nums1[i])
            i++
        } else {
            helper = append(helper, nums2[j])
            j++
        }
    }
    // 将结果 copy 到 nums1
    copy(nums1, helper)
}

编码的话没有啥好说的，完全那种思路来进行实现，但是这里我们需要注意若先遍历完 nums1 或者 nums2 的有序数字部分，那么就将对方还剩下的数字加入到帮助数组中即可

四、总结：

这种解决方式的时间复杂度是多少呢？咱们可以看看咱们循环的次数

虽然是一个死循环，实际上循环的次数还是被我们控制的死死的，其实就是 nums1 的长度， m+n，因此就是咱们的时间复杂度是 O(m+n)

此处咱们引入了一个 helper 数组，数组长度为 m+n，因此占用空间消耗 和 空间复杂都市 O(m+n)

原题地址：[88. 合并两个有序数组](leetcode-cn.com/problems/mi…)

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~