合并兩個有序數組（LeetCode 88）

https://leetcode.cn/problems/merge-sorted-array/?envType=study-plan-v2&envId=top-interview-150

1. 題目背景

你有兩個已經排好序的數組：

• nums1：前面是有效數字，后面是空位（0 占位），用來放另一個數組的元素。
• nums2：完整的、也是排好序的數組。

目標是把 nums2 的元素合并到 nums1 中，并且 最終 nums1 還是升序。

---

例子

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

前 3 個數 [1, 2, 3] 是有效的，后面 3 個 0 是空位。
要把 [2, 5, 6] 填進去，最終得到：

[1, 2, 2, 3, 5, 6]

---

2. 常見但低效的解法

有些同學會這樣做：

1. 把 nums2 直接加到 nums1 的后面。
2. 調用 .sort() 排序。

雖然能跑通，但時間復雜度是 O((m+n) log(m+n))，不夠快。
面試官通常會追問：能不能 O(m+n) 時間完成？

---

3. 高效解法——從尾巴開始合并

關鍵思路

因為兩個數組都是升序的，我們可以用 雙指針 從 尾部 往前填空位。

這樣有兩個好處：

• 不會覆蓋掉還沒處理的數字。
• 不需要移動數組中已有的元素。

---

三個指針的定義

• p1 = m - 1 → 指向 nums1 有效部分的最后一個元素。
• p2 = n - 1 → 指向 nums2 的最后一個元素。
• p = m + n - 1 → 指向 nums1 的最后一個位置（空位）。

---

合并過程（例子推演）

以 nums1 = [1,2,3,0,0,0] 和 nums2 = [2,5,6] 為例：

步驟	p1指向	p2指向	比較	放到 p 位置	數組狀態
1	3	6	6 大	放 6	[1,2,3,0,0,6]
2	3	5	5 大	放 5	[1,2,3,0,5,6]
3	3	2	3 大	放 3	[1,2,3,3,5,6]
4	2	2	一樣大，放 nums2 的 2	[1,2,2,3,5,6]
結束	p2 < 0				完成

---

4. 為什么要 p1 >= 0 判斷？

如果 nums1 的有效部分先用完（p1 < 0），那就不能再訪問 nums1[p1]，否則會越界（尤其在 C++ 里直接崩潰）。
所以我們要保護一下：

if p1 >= 0 and nums1[p1] > nums2[p2]:...
else:...

---

5. Python 實現

def merge(nums1, m, nums2, n):p1 = m - 1p2 = n - 1p = m + n - 1while p2 >= 0:if p1 >= 0 and nums1[p1] > nums2[p2]:nums1[p] = nums1[p1]p1 -= 1else:nums1[p] = nums2[p2]p2 -= 1p -= 1

---

6. C++ 實現

#include <vector>
using namespace std;void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int p1 = m - 1;int p2 = n - 1;int p = m + n - 1;while (p2 >= 0) {if (p1 >= 0 && nums1[p1] > nums2[p2]) {nums1[p] = nums1[p1];p1--;} else {nums1[p] = nums2[p2];p2--;}p--;}
}

---

7. 小結

口訣：

三指針，從尾走，誰大放誰，誰沒了放另一個。

• 從尾往前填空位，不會破壞還沒處理的數字。
• 用 p1 >= 0 防止越界。
• 最終復雜度 O(m+n)，空間 O(1)。