LeetCode Merge Sorted Array：逆序雙指針原地合併

問題描述

有序數組 nums1（長度 m+n，前 m 有效）和 nums2（長度 n）。將 nums2 合併到 nums1，要求 O(1) 額外空間。

逆序雙指針

從後向前填充 nums1：

• i = m-1，j = n-1，k = m+n-1
• 比較 nums1[i] 和 nums2[j]，較大者放入 nums1[k--]
• 若 nums2 剩餘，直接拷貝前綴

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

關鍵點

• 利用 nums1 尾部空閒空間，避免覆蓋未處理元素
• 無需額外數組，真正 O(1) 空間
• 時間 O(m+n)