LeetCode 每日一題：合併兩個有序數組（尾插法）

問題描述

給定兩個有序數組 A（長度 m，尾部有 n 個空位）和 B（長度 n），將 B 合併到 A 中，保持有序。要求原地修改 A。

尾插法（最優）

從後向前比較：ia = m-1, ib = n-1, icur = m+n-1。
while (ia>=0 && ib>=0) A[icur--] = A[ia] > B[ib] ? A[ia--] : B[ib--];
剩餘 B 元素直接複製：while (ib>=0) A[icur--] = B[ib--];
時間 O(m+n)，空間 O(1)，無需輔助數組。

代碼

class Solution {
public:
    void merge(vector<int>& A, int m, vector<int>& B, int n) {
        int ia = m-1, ib = n-1, icur = m+n-1;
        while (ia >= 0 && ib >= 0)
            A[icur--] = A[ia] > B[ib] ? A[ia--] : B[ib--];
        while (ib >= 0) A[icur--] = B[ib--];
    }
};