使用leetcode 怎么合并有序数组

使用leetcode 怎么合并有序数组，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

§ 0x01 题目

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

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

§ 0x02 题目分析

好久没有做过算法题目了。趁清明假期有时间，看陈皓的《极客时间》栏目里推荐刷点leetcode，就来了，刚好是这一道。

这道题是基础题，合并有序数组这样的逻辑是很常见的。比如，归并排序中，最后合并的两个子数组就是有序数组。 最容易想到的就是冒泡和插入排序，但这样的实现显然不是最优的，因为没有利用到两个数组是有序的特性。

一开始我的思路不太清晰。就想着从数组的右侧开始处理，将两个数组合并在一起。实现的时候发现有问题。

1  2 5 0 0
3 4

如上面的两个数组，当处理完5之后，5留下的空位不知道要怎么处理。写了半天也没有想出来怎么处理。查了下有一篇文章的实现挺简单的，不过思路一时间接受不了。https://blog.csdn.net/aka_xyz/article/details/114269364

吃过午饭后，想了下，能否用分治策略呢，仔细一想发现可以。

一开始处理的问题模型为：nums1 m nums2 n。 先比较下nums1和nums2的最大值，也就是最右边的值。

1. 如果nums1的比较大，它就是整个结果中的最大值。将这个最大值放到最终数组的最后，也就是nums1[m+n-1]。问题模型变为nums1 m-1 nums2 n。

2. 如果nums1的比较小或者等于。那么就可以把nums2的最大值，放到最终数组折最后。问题模块变为nums1 m nums2 n-1。

一开始没考虑好极端场景。分治可以自然应对num2中所有值比nums1大的场景，但处理不了num2中所有值都比nums1小的场景。所以要单独处理。

func merge(nums1 []int, m int, nums2 []int, n int) {
        pos := m + n - 1
        p1 := m - 1
        p2 := n - 1
		// 问题模型由p1 p2 nums1 nums2定义
        for p2 >= 0 && p1 >= 0 {
                if nums1[p1] > nums2[p2] {
                        nums1[pos] = nums1[p1]
                        p1--
                        pos--
                } else {
                        nums1[pos] = nums2[p2]
                        p2--
                        pos--
                }
        }

		// 处理极端场景
        if p1 < 0 && p2 >= 0 {
                for i := 0; i <= p2; i++ {
                        nums1[i] = nums2[i]
                }
        }
}

看完上述内容，你们掌握使用leetcode 怎么合并有序数组的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注亿速云行业资讯频道，感谢各位的阅读！