菜鳥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