LeetCode 合併兩個有序數組：逆向雙指針原地合併技巧

正確解法：逆向雙指針 (從後往前)

利用 nums1 末尾的空閒空間，從最大元素開始比較，填充到 nums1 末尾，避免覆蓋未處理數據。

class Solution {
public:
    void merge(vector& nums1, int m, vector& nums2, int n) {
        int i = m - 1;      // nums1 有效元素末尾
        int j = n - 1;      // nums2 有效元素末尾
        int k = m + n - 1;  // 合併後數組末尾
        
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        
        // nums2 剩餘元素直接複製 (nums1 剩餘已在正確位置)
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
};

圖解過程

nums1 = [1,2,3,0,0,0], m=3
nums2 = [2,5,6], n=3

i=2(3), j=2(6), k=5 → 6>3 → nums1[5]=6, j=1, k=4
i=2(3), j=1(5), k=4 → 5>3 → nums1[4]=5, j=0, k=3
i=2(3), j=0(2), k=3 → 3>2 → nums1[3]=3, i=1, k=2
i=1(2), j=0(2), k=2 → 2=2 → nums1[2]=2, j=-1, k=1
j<0 結束，nums1 剩餘 [1,2] 已在正確位置
結果：[1,2,2,3,5,6]

關鍵點解析

複雜度分析

• 時間：O(m+n) - 每個元素最多訪問一次
• 空間：O(1) - 原地修改，僅用常數額外變量

Java 版本 (原題語言)

public class Solution {
    public void merge(int[] nums1, int m, int[] 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--];
        }
        // System.arraycopy(nums2, 0, nums1, 0, j+1); // 處理 nums2 剩餘
        while (j >= 0) nums1[k--] = nums2[j--];
    }
}

舉一反三

此「逆向填充」技巧廣泛適用於：

• 有序數組去重 (從後往前覆蓋)
• 移動零到末尾 (從後往前填非零)
• 原地替換字符串空格為 %20 (從後往前擴展)

核心思想：當目標空間在源空間之後且有足夠緩衝區時，逆向處理避免數據覆蓋。