5、合并两个有序数组。 将两个非递减的有序数组（顺序表），合并为一个非递减的有序数组。 已知两个数组和它们的长度分别为m和n，将第一个数组长度扩展到m+n，多余位置补0，将第二个数组归并到第一个数组上，合并后的数组不需要额外开辟空间。 要求：算法时间复杂程度O(m+n)

算法思路：

可以考虑从后往前遍历两个数组，比较每个位置上的数大小，将较大的数放到第一个数组的末尾，直到将第二个数组中的所有数归并到第一个数组中。

代码实现：

def merge(nums1, m, nums2, n):
    """
    :type nums1: List[int]
    :type m: int
    :type nums2: List[int]
    :type n: int
    :rtype: None Do not return anything, modify nums1 in-place instead.
    """
    i, j, k = m-1, n-1, m+n-1
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    if j >= 0:
        nums1[:k+1] = nums2[:j+1]

测试样例：

nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
merge(nums1, m, nums2, n)
print(nums1)
# 输出 [1, 2, 2, 3, 5, 6]