菜鸟python刷力扣题__3_合并排序的数组

1.描述：

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

2.理解

用python最直接的想法是将B并入到A后面，然后调用sort方法，一开始很怀疑不会通过，结果试了试，发现还真行…

当然，仅仅pass并不是目的。已知该题目中两个序列已经有序，我们可以设置两个指针，分别指向A和B开头，然后比较两个值，根据不同情况对指针进行后移。但是如果直接对A从前往后进行操作显然数据移位时浪费大量时间，而且依据题意，不能使用第三个序列 （这是我的思维误区，其实可以先添加一个序列，最后将结果赋给A就行…）

所以在之前猜想的基础上，我们可以将指针设置成从后往前，每次将最大的数放入A的最末端，此时最坏的时间复杂度为O(n+m)。

3.答题：

3.1简单的想法

class Solution(object):
    def merge(self, A, m, B, n):
        """
        :type A: List[int]
        :type m: int
        :type B: List[int]
        :type n: int
        :rtype: None Do not return anything, modify A in-place instead.
        """
        for i in range(m,m+n):
            A[i]=B[i-m]
        A.sort()
           

执行时间24 ms，消耗内存11.8 MB。

3.2逆双向指针

class Solution(object):
    def merge(self, A, m, B, n):
        """
        :type A: List[int]
        :type m: int
        :type B: List[int]
        :type n: int
        :rtype: None Do not return anything, modify A in-place instead.
        """
        p_a = m-1 # 指向A的有序数字末尾
        p_b = n-1 # 指向B的有序数字末尾
        p = m+n-1 # 指向A序列末尾
        while p_a >= 0 and p_b >= 0: # 当a和b里面数据都未遍历完时
            if A[p_a] > B[p_b]:
                A[p] = A[p_a]
                p -= 1
                p_a -= 1
            else:
                A[p] = B[p_b]
                p -= 1
                p_b -= 1
        while p_a < 0 and p_b >= 0: # 此时是a中的数据已经遍历完
            A[p_b] = B[p_b]
            p_b -= 1
           

执行时间20 ms，消耗内存11.7 MB。

3.3双向指针：利用指针从前往后

class Solution(object):
    def merge(self, A, m, B, n):
        """
        :type A: List[int]
        :type m: int
        :type B: List[int]
        :type n: int
        :rtype: None Do not return anything, modify A in-place instead.
        """
        p_a = 0
        p_b = 0
        p = 0
        result = (m+n)*[0]
        while p_a < m and p_b < n:
            if A[p_a] > B[p_b]:
                result[p] = B[p_b]
                p += 1
                p_b += 1
            else:
                result[p] = A[p_a]
                p += 1
                p_a += 1
        while p_a == m and p_b < n:
            result[p] = B[p_b]
            p += 1
            p_b += 1
        while p_a < m and p_b == n:
            result[p] = A[p_a]
            p += 1
            p_a += 1
        A[:] = result
           

其实后面两种方法原理类似。只不过我的写法有些憨憨…尚且有优化空间。

题目来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/sorted-merge-lcci