2.3 合併兩個有序陣列
88. Merge Sorted Array
題目描述
給定兩個有序陣列,將它們合併為一個陣列。
輸入輸出範例
輸入是兩個陣列和它們分別的長度 m
和 n
。其中第一個陣列的長度被延長至 m + n
,多出的 n
位被 0
填補。題目要求把第二個陣列合併到第一個陣列上,不需要開闢額外空間。
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: nums1 = [1,2,2,3,5,6]
題解
因為這兩個陣列已經排好序,我們可以將兩個指針分別放在兩個陣列的末尾,即 nums1
的 (m - 1)
位和 nums2
的 (n - 1)
位。每次將較大的那個數字複製到 nums1
的後邊,然後向前移動一位。
我們也需要第三個指針來定位 nums1
的末尾,以便進行複製。在以下的代碼裡,我們直接利用 m
和 n
當作兩個陣列的指針,再額外創建一個 pos
指針,起始位置為 m + n - 1
。每次向左移動 m
或 n
的時候,也要向左移動 pos
。注意,如果 nums1
的數字已經複製完,不要忘記繼續複製 nums2
的數字;如果 nums2
的數字已經複製完,剩下的 nums1
的數字不需要改變,因為它們已經排好序。
在 C++ 的題解中,我們使用了 ++
和 --
的小技巧:a++
和 ++a
都會將 a
加 1,但 a++
的返回值為 a
,而 ++a
的返回值為 a + 1
。如果只希望增加 a
的值而不需要返回值,則兩種寫法都可以(++a
在未經編譯器優化的情況下運行速度會略快一些)。
- C++
- Python
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int pos = m-- + n-- - 1;
while (m >= 0 && n >= 0) {
nums1[pos--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
}
while (n >= 0) {
nums1[pos--] = nums2[n--];
}
}
def merge(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
pos = m + n - 1
m -= 1
n -= 1
while m >= 0 and n >= 0:
if nums1[m] > nums2[n]:
nums1[pos] = nums1[m]
m -= 1
else:
nums1[pos] = nums2[n]
n -= 1
pos -= 1
nums1[: n + 1] = nums2[: n + 1]
複雜度分析
- 時間複雜度: ,遍歷
nums1
和nums2
一次。