LeetCode 88. Merge Sorted Array - 雙指針從後向前合併

題目

給兩個已排序整數陣列 nums1 (長度 m+n，前 m 格有效)、nums2 (長度 n)。將 nums2 合併進 nums1，使 nums1 保持非遞減序。要求 O(1) 額外空間。

核心觀察

nums1 尾部有 n 個空位。若從前向後合併，需搬移元素，最壞 O(mn)。改從後向前比較兩陣列尾端較大者，直接填入 nums1 末尾，無需搬移，單趟 O(m+n)。

算法流程

1. i = m-1, j = n-1, k = m+n-1 (三指針)。
2. 當 i≥0 && j≥0：
   　　nums1[k--] = (nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];
3. 若 j≥0 剩餘：while(j>=0) nums1[k--] = nums2[j--]; (i 剩餘無需動作，已在正確位置)。

代碼實作 (C++ / Java / Python)

C++

class Solution {
public:
    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--];
    }
};

Java

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--];
        while (j >= 0) nums1[k--] = nums2[j--];
    }
}

Python

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i, j, k = m-1, n-1, m+n-1
        while i >= 0 and j >= 0:
            nums1[k] = nums1[i] if nums1[i] > nums2[j] else nums2[j]
            k -= 1
            if nums1[i] > nums2[j]: i -= 1
            else: j -= 1
        while j >= 0:
            nums1[k] = nums2[j]
            k -= 1; j -= 1

複雜度

• 時間：O(m+n)，單趟掃描。
• 空間：O(1)，就地修改。

常見錯誤

• 從前向後合併導致覆蓋未處理元素。
• 忘記處理 nums2 剩餘情況 ( nums1 剩餘天然就位)。
• 索引越界：k 初值為 m+n-1 而非 m+n。

延伸思考

若 nums1 空間不夠 (需申請新陣列)，則退化為標準 merge 步驟，空間 O(m+n)。本題關鍵在於利用已分配的尾部空間倒序填充，是「雙指針從後向前」經典模板。