给你两个按非递减顺序排列的整数数组nums1和nums2,另有两个整数m和n,分别表示nums1和nums2中的元素数目。
请你合并nums2到nums1中,使合并后的数组同样按非递减顺序排列。
注意:最终,合并后数组不应由函数返回,而是存储在数组nums1中。为了应对这种情况,nums1的初始长度为m + n,其中前m个元素表示应合并的元素,后n个元素为0,应忽略。nums2的长度为n。
示例1
输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
解释:需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] 。
示例2
输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例3
输入:nums1 = [0], m = 0, nums2 = [1], n = 1
输出:[1]
解释:需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示
- nums1.length == m + n
- nums2.length == n
- 0 <= m, n <= 200
- 1 <= m + n <= 200
- -109 <= nums1[i], nums2[j] <= 109
进阶
你可以设计实现一个时间复杂度为 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.
"""
nums1[m:] = nums2
nums1.sort()
复杂度分析
1、时间复杂度:O((m+n)log(m+n))。
排序序列长度为 m+n,套用快速排序的时间复杂度即可,平均情况为 O((m+n)log(m+n))。2、空间复杂度:O(log(m+n))。
排序序列长度为 m+n,套用快速排序的空间复杂度即可,平均情况为 O(log(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.
"""
sorted = []
p1, p2 = 0, 0
while p1 < m or p2 < n:
if p1 == m:
sorted.append(nums2[p2])
p2 += 1
elif p2 == n:
sorted.append(nums1[p1])
p1 += 1
elif nums1[p1] < nums2[p2]:
sorted.append(nums1[p1])
p1 += 1
else:
sorted.append(nums2[p2])
p2 += 1
nums1[:] = sorted
复杂度分析
1、时间复杂度:O(m+n)。
指针移动单调递增,最多移动m+n次,因此时间复杂度为 O(m+n)。2、空间复杂度:O(m+n)。
需要建立长度为m+n的中间数组sorted。
方法三:逆向双指针
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.
"""
p1, p2 = m - 1, n - 1
tail = m + n - 1
while p1 >= 0 or p2 >= 0:
if p1 == -1:
nums1[tail] = nums2[p2]
p2 -= 1
elif p2 == -1:
nums1[tail] = nums1[p1]
p1 -= 1
elif nums1[p1] > nums2[p2]:
nums1[tail] = nums1[p1]
p1 -= 1
else:
nums1[tail] = nums2[p2]
p2 -= 1
tail -= 1
复杂度分析
1、时间复杂度:O(m+n)。
指针移动单调递减,最多移动m+n次,因此时间复杂度为 O(m+n)。2、空间复杂度:O(1)。
直接对数组 nums1原地修改,不需要额外空间。