LeetCode中如何合并两个有序数组，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。
给定两个有序整数数组 nums1 和 nums2，将nums2合并到nums1中，使nums1成为一个有序数组。如：
设置两个指针分别指向两个数组的起始位置，依次比较大小，每次将最小值放入输出数组中。因为要建立一个数据存放结果或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]
看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注天达云行业资讯频道，感谢您对天达云的支持。