---
title: "88. Merge Sorted Array"
url: "https://laigary.com/interview/coding/88-merge-sorted-array"
type: "note"
section: "coding"
date: "2023-01-27"
updated: "2026-07-26"
tags: ["Two Pointers", "Array", "Classic"]
---

# 88. Merge Sorted Array

[88\. Merge Sorted Array](https://leetcode.com/problems/merge-sorted-array/)

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

## 思路

合併兩個排序好的序列本身不難（見 [21. Merge Two Sorted Lists](/interview/coding/21-merge-two-sorted-lists)），這題真正的考點是那句「**放回 `nums1`**」—— 也就是**原地**。

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

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

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

### 換個方向：從後往前

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

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

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

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

## 解題方向

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

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

```python
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)$ 空間）

```python
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 面試技巧](/interview/coding/python-tips-for-interview)。

## 補充

**合併家族**：

| 題目 | 資料結構 | 合併幾條 | 核心工具 |
|---|---|---|---|
| [21. Merge Two Sorted Lists](/interview/coding/21-merge-two-sorted-lists) | 鏈結串列 | 2 | dummy head + 兩指針 |
| [23. Merge k Sorted Lists](/interview/coding/23-merge-k-sorted-lists) | 鏈結串列 | **k** | heap 或兩兩分治 |
| **88 這題** | **陣列**（原地） | 2 | **從後往前填** |

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

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

## 複雜度

**從起始端到末端**
- 時間 $O(m + n)$ — 每個元素被搬一次
- 空間 $O(m)$ — 複製 `nums1` 的前 `m` 個

**從末端到起始端**
- 時間 $O(m + n)$ — 同上，而且 `nums2` 用完就提前結束
- 空間 $O(1)$ — 只有三個索引

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

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