iT邦幫忙

DAY 22
1

連續30天,挑戰演算法系列 第 22

[Day22] 30 天挑戰演算法 - 合併兩個已排序的陣列

題目來源:Merge Sorted Array

問題:
給予兩個已經排序過的陣列A、B,請試著將 陣列B 合併 到 陣列A 裡去。
你可以假設 陣列A 擁有足夠的空間可以容納 陣列B 裡的元素( 也就是 陣列A 的大小會大於等於 m + n),A、B陣列的大小分別為 m 和 n 。

想法
既然題目說明了這兩個陣列已經排序過了,所以我們只要去比較大小再合併就好了。可是,如果我們從 index 0 開始的話,勢必會遇到一個問題,那就是 插入 元素的問題,這樣一來是必須要一個暫存的地方來存放。不過這樣做效能不是很好!
所以,我們可以換個想法,從尾端開始比較。這樣就不會有 插入 元素的問題,在空間複雜度和時間複雜度上也會有所提升。

題目說,A的陣列大小會大於或等於A+B的陣列大小,因此我們可以不用擔心 IndexOutOfRangeException 的問題,就直接從尾端開始吧!

合併兩個已排序陣列

public void Merge(int[] A, int m, int[] B, int n)
{
    // 因為 A 有 m 個元素,B有 n 個元素
    while (m + n > 0)
    {
        // 當 A 和 B 都有元素時
        if (m > 0 && n > 0)
        {
            // 若 A 的最後一個大於 B 的最後一個
            // 因為 array index 是從 0 開始, 所以 假設有 5 個元素
            // 則第5個元素的 index 就是 4 ( 5-1 )
            if (A[m-1] > B[n-1])
            {
                A[m + n - 1] = A[m-1];
                m -= 1;
            }
            else // 若 B 的最後一個比 A 的最後一個大
            {
                A[m + n - 1] = B[n-1];
                n-=1;
            }
        }
        else if (n > 0) // 當 A 比較完了,剩 B
        {
            A[m + n - 1] = B[n-1];
            n -= 1;
        }
        else // 當 B 比完了,剩 A,不過 A 不用再從自己搬到自己,所以直接減掉 index 即可
        {
            m -= 1;
        }
        
    }
}

如果還是沒感覺,可以看一下這個例子:
假設
A = [1, 3, 5, 7, -1, -1, -1, -1], m = 4 (因為題目說,陣列A 的實際大小會大於等於 m+n,所以我先假設多出來的空間是-1)
B = [2, 4, 6, 8], n = 4

首先 m+n 是 8, m=4, n=4
第一輪: A[m-1] 比 B[n-1] 小,所以把 B[n-1] 放到 A[m+n-1] (記住,index 是從0開始,所以要減 1)
=> A = [1, 3, 5, 7, -1, -1, -1, 8]

目前的 m=4, n=3
第二輪: A[m-1] 比 B[n-1] 大,所以把 A[m-1] 放到 A[m+n-1]
=> A = [1, 3, 5, 7, -1, -1, 7, 8]

以下就以此類推就行了!

到目前為止應該有感覺了吧!! Good!


上一篇
[Day21] 30 天挑戰演算法 - 迴文
下一篇
[Day23] 30 天挑戰演算法 - 加一
系列文
連續30天,挑戰演算法30

尚未有邦友留言

立即登入留言