88. 合并两个有序数组

https://leetcode-cn.com/problems/merge-sorted-array/

解法一：

正向。两个指针分别指向两个数组，从头开始比较合并，取较小的插入nums1缺点在于若发生插入，需要挪动

解法二：

反向。依然用两个指针，再加一个指针指向合并区末尾。从尾开始比较，取较大的插入nums1末尾，不会发生插入挪动。

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, k = m-1, n-1, m+n-1   #i，j分别指向nums1，nums2有效区末尾；k指向nums1末尾
        while i >= 0 and j >= 0:
            if nums1[i] > nums2[j]:     #较大的插入nums1末尾
                nums1[k] = nums1[i]
                k -= 1
                i -= 1
            else:                   #较小的插入nums2末尾
                nums1[k] = nums2[j]
                k -= 1
                j -= 1
        #若i先走完，则继续处理j
        #不用考虑j先走完，因为j走完说明nums2最小的都已经放入nums1，合并完成
        while j >= 0:
            nums1[k] = nums2[j]
            k -= 1
            j -= 1