題目描述
88.合并兩個有序陣列
給你兩個有序整數陣列 nums1 和 nums2，請你將 nums2 合并到 nums1 中，使 nums1 成為一個有序陣列，
說明:
初始化 nums1 和 nums2 的元素數量分別為 m 和 n ，
你可以假設 nums1 有足夠的空間（空間大小大于或等于 m + n）來保存 nums2 中的元素，
示例：
輸入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
輸出:[1,2,2,3,5,6]
題目決議
方法一：暴力法
解題思路
暴力解法就是直接把兩個陣列合并到一個陣列中，完成合并后再進行排序，這種方式沒有利用陣列有序的特性，所以時間復雜度較差，時間復雜度為O((m+n)log(m+n))，
代碼示例
Java：
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 1. 合并陣列
System.arraycopy(nums2, 0, nums1, m, n);
// 2. 陣列排序
Arrays.sort(nums1);
}
復雜度分析
時間復雜度：O((m+n)log(m+n))
空間復雜度：O(1)
方法二：雙指標(從前往后)
解題思路
兩個陣列都是有序陣列，我們可以采用雙指標的方式分別遍歷 nums1 和 nums2 這兩個陣列，使用指標 p1 作為陣列 nums1 的開頭，指標 p2 作為陣列 nums2 的開頭，每次將較小值放入輸出陣列中去，由于 nums1 是用于輸出的陣列，所有先要把 nums1中的元素拷貝一份出來，此時需要O(m)的空間復雜度，
代碼示例
Java：
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 1. 拷貝nums1陣列
int[] temp = new int[m];
System.arraycopy(nums1, 0, temp, 0, m);
// 2. 雙指標從前往后遍歷
int resIdx = 0, p1 = 0, p2 = 0;
while(p1 < m && p2 < n) {
nums1[resIdx++] = temp[p1] < nums2[p2] ? temp[p1++] : nums2[p2++];
}
// 3. 拷貝未比較元素
if (p1 < m) {
System.arraycopy(temp, p1, nums1, p1 + p2, m + n - p1 - p2);
}
if (p2 < n) {
System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
}
}
復雜度分析
時間復雜度：O(m+n)
空間復雜度：O(m)
方法二：雙指標(從后往前)
解題思路
題目中提到nums1中有足夠大的空間存盤 nums1 和 nums2 中的元素，所以 nums1 陣列下標 m-1 后面都是空閑空間，我們可以使用雙指標從后往前的將 nums1 和 nums2 中的較大值放入 nums1 陣列中，
代碼示例
Java：
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 1. 雙指標從后往前遍歷
int resIdx = m + n - 1, p1 = m - 1, p2 = n - 1;
while(i >= 0 && j >= 0) {
nums1[resIdx--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
}
// 2. 拷貝未比較元素
while(p2 >= 0) {
nums1[resIdx--] = nums2[p2--];
}
}
復雜度分析
時間復雜度：O(m+n)
空間復雜度：O(1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/62073.html
標籤：其他
上一篇：滑動視窗（資料結構）