Description
給定兩個已排序的整數陣列
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#
核心思路：從後往前填入，用三個指針分別追蹤 nums1 有效尾端、nums2 尾端、以及填入位置。
- 從前往前合併會覆蓋 nums1 的元素，需要額外空間
- 從後往前合併利用 nums1 尾端的空位，不會覆蓋未處理的元素
- 每次比較兩個陣列的當前最大值，放入 nums1 的最後空位
Approaches#
1: 合併後排序#
- 概念: 把 nums2 複製到 nums1 的後半段，然後整體排序
- 時間複雜度:
O((m+n) log(m+n))- 排序主導 - 空間複雜度:
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#
- 概念: 三個指針從後往前，每次取較大的元素放入 nums1 末尾
- 時間複雜度:
O(m + n)- 每個元素恰好處理一次 - 空間複雜度:
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--
}
}
}不需要處理
p1剩餘的情況，因為 nums1 的前半段本來就在正確位置。只需要把 nums2 剩餘的複製過去。
🔑 Takeaways#
- Pattern: 從後往前的雙指針合併，避免元素覆蓋
- 關鍵技巧: 利用 nums1 的尾部空間作為緩衝區；只需處理 nums2 剩餘的情況，nums1 的元素本就在原位