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

发布时间:2021-08-12 15:34:47 作者:Leah
来源:亿速云 阅读:163

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

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

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

2

 题解

思路:双指针
设置两个指针分别指向两个数组的起始位置,依次比较大小,每次将最小值放入输出数组中。因为要建立一个数据存放结果或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]

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

推荐阅读:
  1. 使用Python怎么合并两个有序数组
  2. 怎么在PHP中合并两个有序数组

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

leetcode

上一篇:怎么用python实现短信轰炸功能

下一篇:LeetCode中怎么实现区域和检索

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》