88. Merge Sorted Array

──────────────────────────────────────────────────────────────────────

88. Merge Sorted Array

這一個題目的要求是給定兩個已經排序好的陣列，兩個陣列分別是 m 和 n，其中第一個陣列比較長，這個比較長的陣列長度是 m + n，其中前面 m 個數字是題目給定已經排序好的數字，後面 n 個數字是 0。題目要求把兩個陣列組合起來並且排序好後，將所有的數字放入到比較長的陣列。

思路

合併兩個排序好的序列本身不難（見 21. Merge Two Sorted Lists），這題真正的考點是那句「放回 nums1」—— 也就是原地。

為什麼不能直接從前面開始寫

如果從索引 0 開始往後填，第一步就會把 nums1[0] 蓋掉 —— 而那個值還沒被讀取。陣列的寫入是破壞性的，這和鏈結串列很不一樣（21 合併時只是改指標，原本的節點內容不會被動到）。

所以有兩條路：要嘛先複製一份保護原始資料，要嘛換個方向寫。

換個方向：從後往前

題目給的那個「nums1 後面剛好有 n 格空位」不是巧合，是提示。

從最大的元素開始填，往索引小的方向走 —— 這樣寫入的位置永遠在兩個讀取指針的右邊，不可能蓋到還沒讀的資料。

為什麼？因為填到位置 p 時，還沒被處理的元素總共有 p 個（nums1 剩 p1+1 個、nums2 剩 p2+1 個，而 p1 + p2 + 2 = p + 1）。它們全部擠在 p 的左邊，空間永遠剛好夠，不會提前碰頭。

這個「從後往前填，避免覆蓋還沒讀的元素」是陣列原地操作的通用手法。

解題方向

從起始端到末端（需要複製一份）

第一個做法很直覺：直接複製比較長的陣列中的前 m 個元素，接著只要執行合併就好。透過一個指針去遍歷第一個陣列，並透過另外兩個指針去遍歷第二個比較短的陣列與複製過的長度為 m 的陣列，並將比較小的數字慢慢放入最長的陣列中。

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums1Copy = nums1[:m]

        i = 0
        j = 0
        k = 0

        while i < m and j < n:
            if nums1Copy[i] < nums2[j]:
                nums1[k] = nums1Copy[i]
                i += 1
            else:
                nums1[k] = nums2[j]
                j += 1
            k += 1

        if i == m:
            nums1[k:] = nums2[j:]
        if j == n:
            nums1[k:] = nums1Copy[i:]

最後那兩個 if 是把剩下的整段接上去 —— 跳出迴圈時最多只有一邊有剩，而它本身已經排序好了，用切片賦值一次搬完。

時間複雜度為 $O(m+n)$，需要額外的 $O(m)$ 個空間來儲存複製的陣列。

從末端到起始端（$O(1)$ 空間）

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1 = m - 1
        p2 = n - 1
        
        for p in reversed(range(m + n)):
            if p2 < 0:
                break
            if p1 >= 0 and nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                nums1[p] = nums2[p2]
                p2 -= 1

三個指針全部從尾端出發：p 是要填的位置、p1 和 p2 分別指向兩個陣列還沒處理的最大值。每次挑大的那個放進 p。

if p2 < 0: break 是關鍵的提前結束。 nums2 用完就代表剩下的都是 nums1 原本的元素，而它們已經在正確的位置上了 —— 完全不用搬。反過來如果 nums1 先用完（p1 < 0），nums2 剩下的還得繼續搬，所以那個條件寫在 if 裡而不是 break。這個不對稱是這版最容易寫錯的地方。

reversed(range(m + n)) 比 range(m + n - 1, -1, -1) 好讀 —— 它字面上就是「從後往前」，見 Python 面試技巧。

補充

合併家族：

題目	資料結構	合併幾條	核心工具
21. Merge Two Sorted Lists	鏈結串列	2	dummy head + 兩指針
23. Merge k Sorted Lists	鏈結串列	k	heap 或兩兩分治
88 這題	陣列（原地）	2	從後往前填

這組對照最值得記的是「為什麼只有 88 要反過來」：串列合併只改指標，寫入不破壞資料；陣列原地合併從前面寫會蓋掉還沒讀的元素。資料結構決定了方向。

同樣「從後往前避免覆蓋」的題目：任何要在陣列尾端預留空間再原地重排的題目都是這個手法。反過來，26. Remove Duplicates from Sorted Array、27. Remove Element 是從前往後寫，因為它們的寫入指針永遠落後於讀取指針，不會超車 —— 方向的選擇取決於「寫的位置會不會追過讀的位置」。

複雜度

從起始端到末端

• 時間 $O(m+n)$ — 每個元素被搬一次
• 空間 $O(m)$ — 複製 nums1 的前 m 個

從末端到起始端

• 時間 $O(m+n)$ — 同上，而且 nums2 用完就提前結束
• 空間 $O(1)$ — 只有三個索引

其中 m、n 分別是兩個陣列的有效長度。

兩者時間相同，差別完全在空間 —— 而題目刻意把 nums1 開成 m + n 長就是在暗示可以做到 $O(1)$。面試時被追問「能不能不用額外空間」，要的就是從後往前那版。