面试题 10.01. 合并排序的数组

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。编写一个方法，将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。

示例:

输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]
  

思路

解法一：

使用双指针遍历两个数组A和B

逆序遍历，元素不会出现覆盖的情况
分为以下四种情况：
- 比较完之后，A先空，则把B剩余的元素都赋值到A数组中
- 比较完之后，B先空，则把A剩余的元素都赋值到A数组中
- 若A[i]的值大于B[j]的值，则取最大值赋值到A数组中
- 若A[i]的值不大于B[j]的值，则取最大值赋值到A数组中

class Solution:
    def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
        """
        Do not return anything, modify A in-place instead.
        """
        x, y = m - 1, n - 1
        tail = m + n -1
        while x >= 0 or y >= 0:
            if x == -1: # A先空
                A[tail] = B[y]
                y -= 1
            elif y == -1: # B先空
                A[tail] = A[x]
                x -= 1
            elif A[x] > B[y]: # A > B
                A[tail] = A[x]
                x -= 1
            else: # A < B
                A[tail] = B[y]
                y -= 1
            tail -= 1
  