給定兩個已排序的整數陣列
nums1（長度 m+n，後 n 個位置為 0）和nums2（長度 n），將nums2合併到nums1中，結果仍為排序狀態。
Example:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6]
Intuition
TIP
核心思路：從後往前填入，用三個指針分別追蹤 nums1 有效尾端、nums2 尾端、以及填入位置。
- 從前往前合併會覆蓋 nums1 的元素，需要額外空間
- 從後往前合併利用 nums1 尾端的空位，不會覆蓋未處理的元素
- 每次比較兩個陣列的當前最大值，放入 nums1 的最後空位
Approaches
1. Merge then Sort — O((m+n) log(m+n)) / O(1)
- Idea: 把 nums2 複製到 nums1 的後半段，然後整體排序
- Time:
O((m+n) log(m+n))- 排序主導 - Space:
O(1)- 原地排序
class Solution {
fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
for (i in 0 until n) {
nums1[m + i] = nums2[i]
}
nums1.sort()
}
}⭐ 2. Two Pointers from the End — O(m + n) / O(1)
- Idea: 三個指針從後往前，每次取較大的元素放入 nums1 末尾
- Time:
O(m + n)- 每個元素恰好處理一次 - Space:
O(1)- 原地操作
class Solution {
fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
var p1 = m - 1
var p2 = n - 1
var p = m + n - 1
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2]) {
nums1[p] = nums1[p1]
p1--
} else {
nums1[p] = nums2[p2]
p2--
}
p--
}
// 若 nums2 還有剩餘元素，複製過去
while (p2 >= 0) {
nums1[p] = nums2[p2]
p2--
p--
}
}
}WARNING
不需要處理 p1 剩餘的情況，因為 nums1 的前半段本來就在正確位置。只需要把 nums2 剩餘的複製過去。
🔑 Takeaways
- Pattern: 從後往前的雙指針合併，避免元素覆蓋
- Key trick: 利用 nums1 的尾部空間作為緩衝區；只需處理 nums2 剩餘的情況，nums1 的元素本就在原位