class Solution:
    def merge(self , A, m, B, n):
        # write code here
        i = m-1
        j = n-1
        k = m+n-1

        while i >= 0 and j >= 0:
            if A[i] > B[j]:
                A[k] = A[i]
                i -= 1
            else:
                A[k] = B[j]
                j -= 1
            
            k -= 1

        while j >= 0:
            A[j] = B[j]
            k -= 1
            j -= 1

解题思路

这个题很巧妙的一点是：A数组有足够的空间且两个数组都是有序的，则我们可以设置三个指针，一个指向m-1，一个指向n-1，一个指向A空间的最后一个即m+n-1。然后遍历两个数组比较大小，并插入数据。需要注意的是，当A数组遍历完成，但B数组还有没有遍历完成的时候，将B数组剩下的元素插入A数组。

复杂度

时间复杂度为O（m+n），空间复杂度为O（1）。