直接合并然后排序 时间复杂度 O((m + n)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.
"""
nums1[m:] = nums2
nums1.sort()
双指针法
借助额外空间 时间复杂度 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, j = 0, 0
sorted = []
while i < m or j < n:
if i == m:
sorted.append(nums2[j])
j += 1
elif j == n:
sorted.append(nums1[i])
i += 1
elif nums1[i] <= nums2[j]:
sorted.append(nums1[i])
i += 1
else:
sorted.append(nums2[j])
j += 1
nums1[:] = sorted
在num1的尾部插入 不需要额外空间 时间复杂度 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, j = m - 1, n - 1
tail_index = m + n - 1
while tail_index >= 0:
if i == -1:
nums1[tail_index] = nums2[j]
j -= 1
elif j == -1:
nums1[tail_index] = nums1[i]
i -= 1
# 注意下 尾部插入时 大的值先插入
# 和从头插入新数组时相反
elif nums1[i] >= nums2[j]:
nums1[tail_index] = nums1[i]
i -= 1
else:
nums1[tail_index] = nums2[j]
j -= 1
tail_index -= 1
