88. 合并两个有序数组
88. 合并两个有序数组
1.题目
2.我的解决方案
注意：题目中的num1是有固定的内存位置的，计算改变了nums1的指向，*后题目验证的时候还是验证的*初的内存空间，所以必须把*终的答案改到这篇内存空间上才能算是正确的
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 = m
while i < len(nums2):
nums1[j] = nums2[i]
i += 1
j += 1
nums1.sort()
时间复杂度: O ( ( m + n ) l o g ( m + n ) ) O((m+n)log(m+n)) O((m+n)log(m+n))
空间复杂度: O ( l o g ( m + n ) ) O(log(m+n)) O(log(m+n))
3.官方的解决方案
代码可以简化
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()
时间复杂度: O ( ( m + n ) l o g ( m + n ) ) O((m+n)log(m+n)) O((m+n)log(m+n))
空间复杂度: O ( l o g ( m + n ) ) O(log(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.
“””
# 使用时间和空间性能都*好的方法
# 都是两个有序数组
cur1, cur2 = m-1, n-1
tail = m + n – 1
while tail >= 0:
if cur2 < 0: # 当cur2排序完成的时候，cur1的排序也完成
break
elif cur1 < 0 or nums2[cur2] > nums1[cur1]: # 当cur1排序完成的时候，cur2的排序不一定完成
nums1[tail] = nums2[cur2]
cur2 -= 1
else:
nums1[tail] = nums1[cur1]
cur1 -= 1
tail
时间复杂度: O ( m + n ) O(m+n) O(m+n)
空间复杂度: O ( 1 ) O(1) O(1)