< 返回技术文档列表

使用leetcode 怎么合并有序数组

发布时间:2021-09-01 01:11:31⊙投诉举报

使用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 怎么合并有序数组的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注血鸟云行业资讯频道,感谢各位的阅读!


/template/Home/Zkeys/PC/Static