題目描述

給定兩個排序後的數組 A 和 B，其中 A 的末端有足夠的緩衝空間容納 B。編寫一個方法，將 B 合併入 A 並排序。

初始化 A 和 B 的元素數量分別為 m 和 n。

示例:

<code>輸入:

A = [1,2,3,0,0,0], m = 3
B = [2,5,6],       n = 3
輸出: [1,2,2,3,5,6]/<code>

解題思路

方法 1: 直接合並後排序

算法

最直觀的方法是先將數組 B 放進數組 A 的尾部，然後直接對整個數組進行排序。

<code>class Solution {

public:

    void merge(vector& A, int m, vector& B, int n) {

        for (int i = 0; i != n; ++i)

            A[m + i] = B[i];

        sort(A.begin(), A.end());

    }

};/<code>

複雜度分析

時間複雜度：O((m+n)log(m+n))

排序序列長度為 m+n，套用快速排序的時間複雜度即可，平均情況為 O((m+n)log(m+n))。

空間複雜度：O(log(m+n))

排序序列長度為 m+n，套用快速排序的空間複雜度即可，平均情況為 O(log(m+n))。

方法 2: 雙指針

算法

方法 1 沒有利用數組 A 與 B 已經被排序的性質。為了利用這一性質，我們可以使用雙指針方法。這一方法將兩個數組看作隊列，每次從兩個數組頭部取出比較小的數字放到結果中。如下面的動畫所示：

我們為兩個數組分別設置一個指針 pa 與 pb 來作為隊列的頭部指針。代碼實現如下：

<code>class Solution {
public:
    void merge(vector& A, int m, vector& B, int n) {
        int pa = 0, pb = 0;
        int sorted[m + n];
        int cur;
        while (pa < m || pb < n) {
            if (pa == m)
                cur = B[pb++];
            else if (pb == n)
                cur = A[pa++];
            else if (A[pa] < B[pb])
                cur = A[pa++];
            else
                cur = B[pb++];
            sorted[pa + pb - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i)
            A[i] = sorted[i];
    }
};/<code>

複雜度分析

時間複雜度：O(m+n)

指針移動單調遞增，最多移動 m+n 次，因此時間複雜度為 O(m+n)。

空間複雜度：O(m+n)

需要建立長度為 m+n 的中間數組 sorted。

方法3：逆向雙指針

算法

實現代碼如下：

<code>class Solution {
public:
    void merge(vector& A, int m, vector& B, int n) {
        int pa = m - 1, pb = n - 1;
        int tail = m + n - 1;
        int cur;
        while (pa >= 0 || pb >= 0) {
            if (pa == -1)
                cur = B[pb--];
            else if (pb == -1)
                cur = A[pa--];
            else if (A[pa] > B[pb])
                cur = A[pa--];
            else
                cur = B[pb--];
            A[tail--] = cur;
        }
    }
};/<code>