LeetCode Merge Sorted Array：原地合併兩個有序陣列

問題描述

給定兩個已排序整數陣列 A、B，將 B 合併到 A 中形成單一有序陣列。A 有足夠空間容納 m+n 個元素（前 m 個有效，後 n 位置空）。

核心洞察：從後向前合併

若從前向後合併，需移動 A 中元素騰出空間，O(mn) 時間。從後向前則直接填入 A 末尾，無需額外空間，O(m+n) 時間。

演算法步驟

1. 三指標：i = m-1（A 有效尾）、j = n-1（B 尾）、k = m+n-1（合併尾）
2. 比較 A[i] 與 B[j]，較大者放入 A[k]，對應指標前移
3. 若 B 未處理完，直接複製剩餘到 A 前段
4. A 剩餘元素已在正確位置，無需處理

Java 完整實作

public class MergeSortedArray {
    public void merge(int[] A, int m, int[] B, int n) {
        int i = m - 1;      // A 有效部分最後索引
        int j = n - 1;      // B 最後索引
        int k = m + n - 1;  // 合併結果最後索引
        
        // 從後向前合併
        while (i >= 0 && j >= 0) {
            if (A[i] > B[j]) {
                A[k--] = A[i--];
            } else {
                A[k--] = B[j--];
            }
        }
        
        // B 有剩餘，直接複製（A 剩餘已在正確位置）
        while (j >= 0) {
            A[k--] = B[j--];
        }
    }
}

關鍵點解析

為何不需要處理 A 的剩餘？

// 當 j < 0 時迴圈結束
// A[0..i] 本來就有序且位於 A[0..i]，無需移動
// 例如：A=[1,3,5,_,_], B=[2,4]
// 合併後：A=[1,2,3,4,5]
// 若 B 先耗盡，A 剩餘 [1,3,5] 已在正確相對位置

邊界情況

複雜度分析

• 時間：O(m + n) —— 每個元素最多被移動/比較一次
• 空間：O(1) —— 原地修改，無額外陣列

C++ 版本

void merge(vector<int>& A, int m, vector<int>& B, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (i >= 0 && j >= 0)
        A[k--] = (A[i] > B[j]) ? A[i--] : B[j--];
    while (j >= 0)
        A[k--] = B[j--];
}

Python 版本

def merge(A, m, B, n):
    i, j, k = m-1, n-1, m+n-1
    while i >= 0 and j >= 0:
        if A[i] > B[j]:
            A[k] = A[i]; i -= 1
        else:
            A[k] = B[j]; j -= 1
        k -= 1
    while j >= 0:
        A[k] = B[j]; j -= 1; k -= 1

延伸：合併 K 個有序陣列

若擴展為合併 k 個有序陣列，可用最小堆維護各陣列當前最小元素，時間 O(N log k)，N 為總元素數。

總結

Merge Sorted Array 展示逆向思維的威力：利用目標陣列的預留空間，從後向前填充，實現 O(1) 空間、O(m+n) 時間的最優原地合併。此技巧廣泛應用於歸併排序優化、資料庫合併、外部排序等場景。