每日一题开始！有学python的小伙伴一起嘛

image.png

看来今天做的蛮早的，竟然击败了这么多人

难度：简单

题目内容：

给定两个排序后的数组 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在原址上排序的话，他的最后几位肯定是干净的什么也没有的，就是实例中0的部分。
依次比较A未排序数字的最后一个，也就是A未排序的最大值以及B未排序的最大值，哪个大就把它放到最大值应该去的地方，然后最大值的指针向前走一格，被拿走数字的序列的指针也往前走一格，直到排序完成。

代码

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.
        """
        i = n - 1 #指向B的最后一个，最大值
        j = m - 1 #指向A的最后一个，最大值
        last = n+m-1 #待排的最大值的位置
        #从最大的，最后一个开始排
        while i >= 0:   #如果i是B的索引0~n-1，如果小于0 说明插入完成
            if j == -1: #当A内的元素被排完，只有B没有排，就放入A中
                A[0:i+1] = B[0:i+1]
                break
            if B[i] >= A[j]:
                A[last] = B[i]
                i -= 1
            elif B[i] < A[j]:
                A[last] = A[j]
                j -= 1
            last -= 1