一、題目介紹
今天要解的題目是LeetCode的Merge Sorted Array，中文可以稱為「合併兩個有序陣列」。

題目會給定兩個已經按照非遞減順序排列的整數陣列nums1, nums2
其中nums1已經預留足夠的空間，可以容納nums2中的元素。

題目會提供
m = nums1 中原本有效元素的數量
n = nums2 中元素的數量
需要將nums2合併到nums1中，並且讓最後的nums1仍然保持排序

例如
nums1 = [1, 2, 3, 0, 0, 0]
m = 3

nums2 = [2, 5, 6]
n = 3

其中nums1前三個元素[1, 2, 3]是原本有效的資料
後面的[0, 0, 0]只是預留給nums2使用的空間

合併之後[1, 2, 2, 3, 5, 6]

二、解題思路
這題可以使用Two Pointers（雙指標）解決

其實這題和Day 04的Two Pointers有一點不同
Day 04是左指標 → ← 右指標
從兩端向中間靠近

而今天則是使用三個指標
p1：指向nums1原本有效資料的最後一個元素
p2：指向nums2的最後一個元素
p：指向nums1最後一個位置

三、解題流程
以以下為例
nums1 = [1, 2, 3, 0, 0, 0]
m = 3

nums2 = [2, 5, 6]
n = 3

一開始
p1 = 2
p2 = 2
p = 5

Step 1：比較3和6
nums1[p1] = 3
nums2[p2] = 6

因為6 > 3
所以把6放到最後面[1, 2, 3, 0, 0, 6]

Step 2：比較3和5
3 < 5
所以將5放到目前最後的位置[1, 2, 3, 0, 5, 6]

Step 3：比較3和2
nums1[p1] = 3
nums2[p2] = 2

因為3 > 2
所以把3放入目前的位置[1, 2, 3, 3, 5, 6]

Step 4：比較2和2
兩個值相同
nums1[p1] = 2
nums2[p2] = 2

可以將nums2的2放入[1, 2, 2, 3, 5, 6]
最後完成合併

四、Java實作

五、Python實作

六、時間與空間複雜度
Java

• 時間複雜度：O(m + n)
  • nums1原本有m個有效元素，nums2有n個元素。
  • 每個元素最多被處理一次，因此時間複雜度為：O(m + n)
• 空間複雜度：O(1)
  • 只使用p1、p2、p三個指標，沒有建立額外陣列或其他資料結構。
  • 因此空間複雜度為：O(1)

Python

• 時間複雜度：O(m + n)
  • 兩個陣列中的元素最多各處理一次，因此時間複雜度為：O(m + n)
• 空間複雜度：O(1)
  • 只使用幾個指標變數，直接修改nums1，沒有建立額外的陣列。
  • 因此為：O(1)

七、Java與Python解法比較

八、實作結果
Leetcode測試結果：Accepted

九、今日學習心得
今天學習的Merge Sorted Array讓我再次練習Two Pointers（雙指標），也了解到雙指標不一定只能從陣列的左右兩端向中間移動，也可以根據題目的需求，從陣列尾端開始進行處理。

這題最重要的地方是觀察nums1已經預留了足夠的空間，因此可以直接從最後面開始放入元素。透過比較兩個陣列目前最大的元素，將較大的值放到nums1的最後面，再讓指標向前移動。

如果從前面開始合併，可能會覆蓋掉nums1中尚未處理的資料；而從後面開始則可以充分利用題目提供的空間。

這讓我了解到，解題時除了要思考「使用哪一種演算法」，也需要觀察題目提供的資料結構與限制。有時候題目特別預留的空間，其實就是提示我們可以利用原地（In-place）操作完成問題。

今天也進一步理解了Space Complexity O(1)的意義。雖然陣列本身已經存在，但程式並沒有另外建立新的陣列，而是直接修改原本的nums1，因此不需要額外的線性空間。