# 【LeetCode刷題】【演算法學習筆記】88. Merge Sorted Array
* 學習時間：2025/2/5 (wed.)
* **題目連結（美服）：** [88. Merge Sorted Array](https://leetcode.com/problems/merge-sorted-array/description/)
* **題目連結（國服）：**[88. 合并两个有序数组](https://leetcode.cn/problems/merge-sorted-array/)
* **題目標籤：** ==陣列== ==雙指針== ==排序==
### A. 題目
---
You are given two integer arrays ==nums1== and ==nums2==, sorted in **non-decreasing order**, and two integers ==m== and ==n==, representing **the number of elements** in nums1 and nums2 respectively.
**Merge** nums1 and nums2 into a single array sorted in **non-decreasing order**.
The final sorted array should not be returned by the function, but instead **be stored inside the array nums1**.
To accommodate this, nums1 has a length of m + n, where the first ==m== **elements denote the elements that should be merged**, and the last n elements are set to 0 and should be ignored. **nums2 has a length of ==n==**.
Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].
Example 3:
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.
### B. 題目（中文）
---
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
**示例 1：**
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
**示例 2：**
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
**示例 3：**
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
### C. 參考程式碼
---
:::spoiler Solution & Thinking（力扣官方思路）
* reference: [力扣官方题解](https://leetcode.cn/problems/merge-sorted-array/solutions/666608/he-bing-liang-ge-you-xu-shu-zu-by-leetco-rrb0/)
**題解一**
* 思路：使用**雙指針**
* 程式實現：
1. 利用陣列已經排序的特性 ➡︎ 使用**雙指針**
2. 每次從兩陣列第一個元素**比較大小**，大的元素輸出欲合併陣列 **ans**
```python=
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
# 儲存合併後的結果的新陣列
ans = []
# 初始化指針指向兩陣列第一個元素
p1, p2 = 0, 0
# 只要 nums1 或 nums2 還沒完全處理完，就繼續執行迴圈。
while p1 < m or p2 < n:
# 特殊狀況 p1 或 p2 拜訪完
if p1 == m:
ans.append(nums2[p2])
p2 += 1
elif p2 == n:
ans.append(nums1[p1])
p1 += 1
# 比較兩陣列元素大小
elif nums1[p1] < nums2[p2]:
ans.append(nums1[p1])
p1 += 1
else:
ans.append(nums2[p2])
p2 += 1
# 保留 nums1 原本的記憶體位置
# 修改 nums1 的內容，讓它變成 ans 的結果
nums1[:] = ans
```
**複雜度**
* Time complexity: **O(m+n)**
* Space complexity: **O(m+n)**
---
**題解二**
* 思路：使用**逆向的雙指針**
* 優化：在合并 nums2 到 nums1 时，如果我们直接从前往后插入，就**会覆盖掉 nums1 还未处理的元素**。因此，我们 倒着填充 nums1 的最后位置，这样就不会破坏 nums1 还未处理的数据。
* 核心思路：
1. 设 p1 指向 nums1 的有效部分的最后一个元素（即==m-1==）。
2. 设 p2 指向 nums2 的最后一个元素（即==n-1==）。
3. 设 tail 指向 nums1 的最后一个位置（即==m+n-1==）。
从后往前填充 nums1，每次选 nums1[p1] 和 nums2[p2] 较大的那个放入 nums1[tail]，然后指针前移。合併陣列 **ans**
```python=
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
# 指標初始化
p1, p2 = m - 1, n - 1
# 答案陣列 nums1 尾端索引
tail = m + n - 1
while p1 >= 0 or p2 >= 0:
# 特殊狀況 p1 或 p2 拜訪完
if p1 == -1:
nums1[tail] = nums2[p2]
p2 -= 1
elif p2 == -1:
nums1[tail] = nums1[p1]
p1 -= 1
# 比較兩陣列元素大小
elif nums1[p1] > nums2[p2]:
nums1[tail] = nums1[p1]
p1 -= 1
else:
nums1[tail] = nums2[p2]
p2 -= 1
# 每處理一個數字，tail 也要向左移
tail -= 1
```
**複雜度**
* Time complexity: **O(m+n)** 最差的狀況是，每個數都需移動一次
* Space complexity: **O(1)**，僅使用到一些額外變量
:::
:::spoiler Solution & Thinking（靈神官方思路）
**靈神題解**
* reference:[灵茶山艾府](https://leetcode.cn/problems/merge-sorted-array/solutions/2385610/dao-xu-shuang-zhi-zhen-wei-shi-yao-dao-x-xxkp/)
* 解題思路
1. nums1 有 m 個有效數字，nums2 有 n 個有效數字。
2. nums1 陣列的大小是 m + n，後面 n 個位置是空的，讓我們可以直接合併 nums2 進來。
3. **從後往前填充：** 因為兩個陣列都是排序好的，最大值一定在最後面，所以我們從 最大值開始放，避免覆蓋掉還沒處理的數據。
* 算法實現
1. 初始化三個指針：
* 指向 nums1: p1 = m-1
* 指向 nums2: p2 = n-1
* 指向 ans: p = m+n-1
2. 不斷比較 nums1[p1] 和 nums2[p2]，比較大的放入nums1[p]，循環直到 p < 0
```python=
from typing import List
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
# 指標初始化
p1, p2 = m - 1, n - 1
# 答案陣列尾端索引
tail = m + n - 1
while p2 >= 0: # nums2 還有要合併的元素
# nums1 還有要合併的元素 且 nums1[p1] > nums2[p2]
if p1 >= 0 and nums1[p1] > nums2[p2]:
nums1[tail] = nums1[p1]
p1 -= 1
else: # nums1[p1] <= nums2[p2] 或 p1 < 0
nums1[tail] = nums2[p2]
p2 -= 1
tail -= 1 # 下一個要填入的位置
```
**複雜度**
* Time complexity: **O(m+n)** 最差的狀況是，每個數都需移動一次
* Space complexity: **O(1)**，僅使用到一些額外變量
:::
Sign in with Wallet
Connect another wallet