88. 合併兩個有序陣列
EasyMerge Sorted Array
ArrayTwo Pointers
題目描述
給定兩個已排序的整數陣列 nums1 和 nums2，將 nums2 合併到 nums1 中，使合併後的陣列仍然有序。nums1 的後半段預留了足夠空間（以 0 填充）。
LeetCode 88原題連結 →解法思路
- 使用三指針：p1 指向 nums1 有效元素末尾、p2 指向 nums2 末尾、p 指向 nums1 最末端
- 從後往前填充，比較 nums1[p1] 和 nums2[p2]，將較大者放到 nums1[p]
- 避免從前往後合併時需要搬移元素的問題
- 當 p2 < 0 時結束（nums1 剩餘部分已在正確位置）
複雜度分析
- 時間複雜度：O(m + n)
- 空間複雜度：O(1)
nums1（含預留空間）
1
[0]2
[1]3
[2]0
[3]0
[4]0
[5]p1 = 2p = 5
nums2
2
[0]5
[1]6
[2]填入位置 (p)nums1 指針 (p1)nums2 指針 (p2)
初始狀態：nums1 有效長度 m=3，nums2 長度 n=3。三個指針：p1=2（nums1 末尾），p2=2（nums2 末尾），p=5（填入位置）。
1 / 10