ROSALIND｜Merge Two Sorted Arrays (MER)

發表於

給定兩個有序的整數數列，求一個含有兩數列所有數字的有序數列。

Given: A positive integer $n \leq 10^5$ and a sorted array $A[1..n]$ of integers from $-10^5$ to $10^5$, a positive integer $m \leq 10^5$ and a sorted array $B[1..m]$ of integers from $-10^5$ to $10^5$.

Return: A sorted array $C[1..n+m]$ containing all the elements of $A$ and $B$.

(https://rosalind.info/problems/mer/)

假設兩數列皆為遞增數列，只要逐一比較它們最前端的數字，將較小者納入輸出數列，重複此過程直到所有數字都被取出，即可獲得一個含有所有數字的遞增數列。

具體的做法是用 merged 儲存輸出序列，並用 s 和 t 追蹤要比較的數字位置。當其中一個數列的數字全被取出時，另一個數列剩餘的數字都會比輸出數列的數字大，所以可以直接銜接到輸出數列後方。

1
2
3
4
# 像這樣，T 可以放心接在 out 後面
S = []
T = [4, 5, 6] 
out = [1, 2, 3]

因此，在迴圈之後必須處理剩餘數字，以免輸出數列遺漏部分片段。另外，迴圈要以 and 為條件。如果用 or，在其中一個數列的數字都被取出後，指標還會持續增加，導致位置超出範圍。這個做法為線性時間和空間複雜度。

1
2
3
4
5
6
7
8
9
10
11
12
13
def mer(S, T):
    merged = []
    s, t = 0, 0
    while s < len(S) and t < len(T):  # 用 or 會怎樣？
        if S[s] <= T[t]:
            merged.append(S[s])
            s = s + 1
        else:
            merged.append(T[t])
            t = t + 1
    merged.extend(S[s:]) # 為什麼要補這兩行？
    merged.extend(T[t:])
    return merged

遞迴方法的概念與迴圈方法類似，都是比較兩數列最小的數字，取較小者納入輸出數列，其餘數列則遞迴處理。為了方便，這裡用 list slicing 處理剩餘數列。list slicing 的時間複雜度為 O(k)（參考 https://wiki.python.org/moin/TimeComplexity#list），加上遞迴要遍歷兩數列的所有數字，整體變成平方時間複雜度。

1
2
3
4
5
6
7
8
9
def mer_rc(S, T):
    if not S:
        return T
    if not T:
        return S
    if S[0] <= T[0]:
        return [S[0]] + mer_rc(S[1:], T)
    else:
        return [T[0]] + mer_rc(S, T[1:])