LeetCode in Python 88. Merge Sorted Array (合并两个有序数组)

合并有序数组也有两种方法，区别是空间复杂度不同。第一种，重新开辟一个数组空间，大小为O(m+n)，另外需要三个指针分别指向两个有序数组和新开辟的数组，依次判断两个数组内元素大小，不断更新指针即可。第二种，无需单独开辟空间，在第一个数组(该数组空间足够存放两个数组总长的数据)内进行操作，仍然需要三个指针，可从尾部开始合并，因此需要尾指针和分别指向两数组的指针。

示例：

图1 数组合并示意图 

代码：

class Solution:
    def merge(self, nums1, m, nums2, n):
        last = m + n - 1
        while m and n:
            if nums1[m-1] > nums2[n-1]:
                nums1[last] = nums1[m-1]
                m -= 1
            else:
                nums1[last] = nums2[n-1]
                n -= 1
            last -= 1
        
        if n:
            nums1[:n] = nums2[:n]
        return nums1

 注意：

1）last、m、n分别对应尾指针和指向两个数组的指针

2）当出现nums1第一个元素大于nums2第一个元素时，在nums1遍历完后nums2还有剩余，由于两个数组均为升序排列，故只需把nums2剩余的n个数组元素挪到nums1前n个元素即可。

        if n:

                nums1[:n] = nums2[:n]