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<m and j<n:            if nums3[i]<=nums2[j]:                nums1.append(nums3[i])                i += 1            else :                nums1.append(nums2[j])                j += 1        if i<m:            nums1[i+j:]=nums3[i:]        if j<n:            nums1[i+j:]=nums2[j:]

进一步将空间复杂度从 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中如何合并两个有序数组
转载源于：https://www.cdcxhl.com/article40/gejieo.html

成都网站建设公司_创新互联，为您提供虚拟主机、品牌网站建设、企业网站制作、网页设计公司、定制网站、响应式网站

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：创新互联

猜你还喜欢下面的内容