合并排序数组（简单版）

描述

合并两个排序的整数数组 A 和 B 变成一个新的数组。 原地修改数组 A 把数组 B 合并到数组 A 的后面。

---

你可以假设A具有足够的空间（A数组的大小大于或等于m+n）去添加B中的元素。数组A和B分别含有m和n个数。

样例

样例 1：

输入：

A = [1,2,3]m = 3B = [4,5]n = 2

输出：

[1,2,3,4,5]

解释：

经过合并新的数组为[1,2,3,4,5] 样例 2：

输入：

A = [1,2,5]m = 3B = [3,4]n = 2

输出：

[1,2,3,4,5]

解释：

经过合并新的数组为[1,2,3,4,5]

解题思路：

该问题是合并两个已经排序的数组A和B。由于A数组有足够的空间容纳两个数组的元素，并且从后往前填充数组使得操作更简单方便。可以采用双指针的方法，同时从A和B的最后一个元素开始比较，逐步向前移动，并将较大的元素放入A数组的末尾。当一个指针耗尽时，将另一个数组剩余的元素直接复制到A中即可完成合并。这样最终得到一个新的有序数组。

class Solution:
    """
    @param: A: sorted integer array A which has m elements, but size of A is m+n
    @param: m: An integer
    @param: B: sorted integer array B which has n elements
    @param: n: An integer
    @return: nothing
    """
    def mergeSortedArray(self, A, m, B, n):
        # write your code here
        # 双指针,从A尾部开始填充，想着耗尽数组即可，所以while比的总是两个数组尺寸，看耗尽没有。
        p,q = m-1,n-1
        cur = m+n-1
        while cur > -1:
            if p == -1:
                A[cur] = B[q]
                q -= 1
            elif q == -1:
                A[cur] = A[p]
                p -= 1
            elif A[p] > B[q]:
                A[cur] = A[p]
                p -= 1
            else:
                A[cur] = B[q]
                q -= 1
            cur -= 1