LeetCode 合併兩個有序陣列：原地合併演算法詳解

題目描述

給定兩個已排序的整數陣列 nums1 和 nums2，請將 nums2 合併到 nums1 中，使合併後的陣列仍保持有序。

關鍵條件：

• nums1 擁有足夠的空間容納 nums2 的所有元素（即 nums1.length == m + n）
• nums1 的有效長度為 m，nums2 的有效長度為 n
• 必須在 nums1 上原地修改，不返回任何值

範例：

輸入: nums1 = [1, 1, 2, 2, 4, 0, 0, 0, 0], m = 5
      nums2 = [0, 0, 2, 3], n = 4
輸出: nums1 變為 [0, 0, 1, 1, 2, 2, 2, 3, 4]

解題思路：逆向雙指針法

既然兩個陣列都是有序的，且 nums1 尾部有足夠空間，我們可以從後向前遍歷，避免覆蓋 nums1 中尚未處理的元素。

1. 初始化三個指針：index = m + n - 1（合併後陣列的最後位置）、i = m - 1（nums1 有效元素末尾）、j = n - 1（nums2 末尾）
2. 當 i >= 0 且 j >= 0 時，比較 nums1[i] 和 nums2[j]，將較大者放入 nums1[index]，並移動相應指針
3. 若 nums2 還有剩餘元素（j >= 0），直接複製到 nums1 前段；若 nums1 有剩餘則無需操作，因為它們已在正確位置

時間複雜度：O(m + n)，空間複雜度：O(1)。

Python 參考實現

class Solution:
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        index = m + n - 1
        i, j = m - 1, n - 1
        
        while i >= 0 and j >= 0:
            if nums1[i] > nums2[j]:
                nums1[index] = nums1[i]
                i -= 1
            else:
                nums1[index] = nums2[j]
                j -= 1
            index -= 1
        
        # 若 nums2 有剩餘，直接複製
        if j >= 0:
            nums1[:j + 1] = nums2[:j + 1]

# 測試
if __name__ == "__main__":
    nums1 = [1, 1, 2, 2, 4, 0, 0, 0, 0]
    nums2 = [0, 0, 2, 3]
    Solution().merge(nums1, 5, nums2, 4)
    assert nums1 == [0, 0, 1, 1, 2, 2, 2, 3, 4]
    print("測試通過：", nums1)

核心要點總結

• 逆向思維：利用 nums1 尾部空間，從大到小填充，避免數據覆蓋
• 邊界處理：只需處理 nums2 的剩餘元素，nums1 的剩餘元素天然就位
• 原地修改：滿足題目「不返回值、原地修改」的硬性要求

這道題是雙指針技巧的經典應用，掌握「從後向前」的合併策略，能輕鬆解決類似的有序陣列合併問題。