LeetCode刷题DAY 22：合并两个有序数组
难度：简单 关键词：双指针
⭐️⭐️⭐️
1
题目描述
给定两个有序整数数组 nums1 和 nums2，将nums2合并到nums1中，使nums1成为一个有序数组。如：
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]
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-05-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读