from typing import List
#--------testcase input---------
l1a = [1,2,3,0,0,0]
l1b = [2,5,6]
#----------------------------main function--------------------------------
# V1.0 要求原地修改，从后往前比较，并从后往前插入
# def merge(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
# i = 0
# while m > 0 and n > 0:
# i += 1
# if nums1[m-1] > nums2[n-1]:
# nums1[-i] = nums1[m-1]
# m -= 1
# else:
# nums1[-i] = nums2[n-1]
# n -= 1
# if m == 0 and n > 0:
# while n > 0:
# i += 1
# nums1[-i] = nums2[n-1]
# n -= 1
# else:
# while m > 0:
# i += 1
# nums1[-i] = nums1[m-1]
# m -= 1
# V1.1: 比较聪明的写法
#时间复杂度：O()
#空间复杂度：O()
def merge(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
while m > 0 and n > 0:
if nums1[m-1] > nums2[n-1]:
nums1[m+n-1] = nums1[m-1]
m -= 1
else:
nums1[m+n-1] = nums2[n-1]
n -= 1
if n > 0: #这样写法不必考虑m>0 && n==0的情况，因为是从m+n-1位置开始从后往前写，而不是像V1.0从nums1数组的最后一个位置往前写，故此时不用做任何处理
while n > 0:
nums1[m+n-1] = nums2[n-1]
n -= 1
#--------testcase output---------
merge(l1a,3,l1b,3)
print(l1a)
