LeetCode 88：合併兩個有序數組——逆向雙指針

題目描述

有序數組 A（長度 m）有足夠空間容納 B（長度 n），將 B 合併到 A 中保持有序。

逆向雙指針法

從尾部開始比較，大的放在 A 的末尾，避免覆蓋未處理元素：

void merge(int A[], int m, 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--]; // B 剩餘直接複製
}

關鍵點

• 不需要額外空間，O(1) 空間
• 只需處理 B 剩餘情況，A 剩餘已在正確位置
• 時間 O(m+n)