LeetCode 經典：有序數組合併（從尾部開始的 O(1) 空間解法）

題目描述

給定兩個已排序數組 A、B，其中 A 尾部預留足夠空間容納 B。請將 B 合併到 A 中並保持有序，要求 原地修改 A，空間複雜度 O(1)。

核心思路：逆向雙指針

若從頭部合併，需搬移 A 中元素，時間複雜度退化。利用 A 尾部空閒空間，從最大值開始比較，填入 A 末尾，避免覆蓋未處理數據。

算法步驟

1. 三指針：indexA = lastA - 1、indexB = lastB - 1、mergeIndex = lastA + lastB - 1。
2. 比較 A[indexA] 與 B[indexB]，較大者放入 A[mergeIndex]，對應指針前移。
3. 若 B 剩餘元素未處理完，直接拷貝至 A 前部（A 剩餘元素已在正確位置）。

完整代碼實現

public class MergeSortedArray {
    /**
     * @param a 目標數組（含尾部預留空間）
     * @param b 來源數組
     * @param lastA a 中實際有效元素個數
     * @param lastB b 中實際有效元素個數
     */
    public static void mergeOrder(int[] a, int[] b, int lastA, int lastB) {
        int indexA = lastA - 1;
        int indexB = lastB - 1;
        int mergeIndex = lastA + lastB - 1;

        while (indexA >= 0 && indexB >= 0) {
            if (a[indexA] > b[indexB]) {
                a[mergeIndex--] = a[indexA--];
            } else {
                a[mergeIndex--] = b[indexB--];
            }
        }

        // B 剩餘元素直接拷貝
        while (indexB >= 0) {
            a[mergeIndex--] = b[indexB--];
        }
    }
}

複雜度分析

• 時間複雜度：O(m + n)，單次遍歷。
• 空間複雜度：O(1)，原地修改，無額外數組。

擴展思考

• 若 A 空間不足，需申請新數組，空間變為 O(m+n)。
• 同理可解決「合併兩個有序鏈表」等變體題目。
• 面試中常考察「為何從尾部開始」，關鍵點在於利用已知空閒空間避免數據搬移。