每日一题-3

题目描述

给定两个排序后的数组 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]

解题思路

1.暴力法
这个方法最容易想到，时间复杂度也大一些。由于A中后面刚好留出容纳B数组的空间，所以可直接将B赋值到A的后面，然后对A进行排序。这种方法没有利用到已知条件给出的A和B都是已经排序好的数组，根据这个条件，可以设计出下面这种方法。
2.三指针
这种想法有点像两个已经排好序数组合并成一个数组，时间复杂度都为O(m+n)。合并数组一般是在数组开头设置指针，哪一个数组指向的数小，则追加到新数组当中，通知指针后移一位。
对于本题，因为A数组已经留好了空间，为了空间复杂度最小，则不设置新数组，而采用末尾三指针，多设置一个赋值指针，从后往前对A进行赋值。
indexA,indexB初始时指向A,B的非零末尾，cur指向数组A的实际末尾
indexA和indexB用来反向遍历A，B、cur进行赋值

代码

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.
        """
        #末尾双指针
        indexA = m-1
        indexB = n-1
        cur = m+n-1
        while(indexA>-1 and indexB>-1):#A,B越界为结束条件
            if(A[indexA]>B[indexB]):#如果A的末尾元素大于B的末尾元素
                A[cur] = A[indexA]
                indexA-=1
                cur-=1
            else:
                A[cur] = B[indexB]
                indexB-=1
                cur-=1
        #如果B还有剩余，则将其全部放在A的前面即可
        if(indexB>-1):
            A[:indexB+1] = B[:indexB+1]