LeetCode中如何合并两个有序数组

LeetCode中如何合并两个有序数组，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。

公司主营业务：网站设计、成都网站设计、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。成都创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。成都创新互联推出平定免费做网站回馈大家。

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

LeetCode中如何合并两个有序数组

题解

思路：双指针

设置两个指针分别指向两个数组的起始位置，依次比较大小，每次将最小值放入输出数组中。因为要建立一个数据存放结果或nums1，所以空间复杂度最小为O（m），时间复杂度则为O（m+n）。

class Solution:       def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:        """        Do not return anything, modify nums1 in-place instead.        """        i = 0        j = 0        nums3 = nums1[0:m]        nums1[:] = []        while i

进一步将空间复杂度从 O（m ）缩减至O（1），可考虑从右至左依次比较，每次将最大值从右边依次放入输出数组中，此时要增加一个指针记录放入的位置。时间复杂度依旧是为 O（m+n ）。

class Solution:    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:        """        Do not return anything, modify nums1 in-place instead.        """        i = m-1        j = n-1        z = m+n-1        while i>=0 and j>=0:            if nums1[i]<=nums2[j]:                nums1[z]=nums2[j]                j -= 1            else :                nums1[z]=nums1[i]                i -= 1            z -= 1        if j >= 0:            nums1[:j+1]=nums2[:j+1]

看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注创新互联行业资讯频道，感谢您对创新互联的支持。

网站栏目：LeetCode中如何合并两个有序数组
本文来源：http://cdiso.cn/article/gejieo.html

LeetCode中如何合并两个有序数组

其他资讯