公司網(wǎng)站建設(shè)合同書網(wǎng)絡(luò)推廣網(wǎng)站公司
- 🎈個人主頁:庫庫的里昂
- ?🎐C/C++領(lǐng)域新星創(chuàng)作者
- ?🎉歡迎 👍點贊?評論?收藏
- ?收錄專欄:LeetCode 刷題日志
- 🤝希望作者的文章能對你有所幫助,有不足的地方請在評論區(qū)留言指正,大家一起學習交流!🤗
目錄
1.題目描述
2.解題思路+代碼實現(xiàn)
方法一:直接合并后排序
思路及算法:
代碼實現(xiàn):
方法二:雙指針
思路及算法:
代碼實現(xiàn):
方法三:逆向雙指針
思路及算法:
代碼實現(xiàn):
1.題目描述
OJ鏈接?【leetcode?題號:88.合并兩個有序數(shù)組】【難度:簡單】
給你兩個按?非遞減順序?排列的整數(shù)數(shù)組?nums1
?和?nums2
,另有兩個整數(shù)?m
?和?n
?,分別表示?nums1
?和?nums2
?中的元素數(shù)目。
請你?合并?nums2
?到?nums1
?中,使合并后的數(shù)組同樣按?非遞減順序?排列。
注意:最終,合并后數(shù)組不應(yīng)由函數(shù)返回,而是存儲在數(shù)組?nums1
?中。為了應(yīng)對這種情況,nums1
?的初始長度為?m + n
,其中前?m
?個元素表示應(yīng)合并的元素,后?n
?個元素為?0
?,應(yīng)忽略。nums2
?的長度為?n
?。
示例 1:
輸入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 輸出:[1,2,2,3,5,6] 解釋:需要合并 [1,2,3] 和 [2,5,6] 。 合并結(jié)果是 [1,2,2,3,5,6] ,其中斜體加粗標注的為 nums1 中的元素。
示例 2:
輸入:nums1 = [1], m = 1, nums2 = [], n = 0 輸出:[1] 解釋:需要合并 [1] 和 [] 。 合并結(jié)果是 [1] 。
示例 3:
輸入:nums1 = [0], m = 0, nums2 = [1], n = 1 輸出:[1] 解釋:需要合并的數(shù)組是 [] 和 [1] 。 合并結(jié)果是 [1] 。 注意,因為 m = 0 ,所以 nums1 中沒有元素。nums1 中僅存的 0 僅僅是為了確保合并結(jié)果可以順利存放到 nums1 中。
提示:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
進階:你可以設(shè)計實現(xiàn)一個時間復雜度為?O(m + n)
?的算法解決此問題嗎?
2.解題思路+代碼實現(xiàn)
方法一:直接合并后排序
思路及算法:
這種方法最直觀,先將數(shù)組nums2放進數(shù)組nums1的尾部,然后直接對整個數(shù)組進行排序。
代碼實現(xiàn):
int cmp(int* a, int* b) {return *a - *b;
}void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {for (int i = 0; i != n; ++i) {nums1[m + i] = nums2[i];}qsort(nums1, nums1Size, sizeof(int), cmp);
}
復雜度分析
- 時間復雜度:O((m+n)log(m+n))。 排序序列長度為m+n,套用快速排序的時間復雜度即可,平均情況為O((m+n)log(m+n))。
- 空間復雜度:O(log(m+n))。排序序列長度為m+n,套用快速排序的空間復雜度即可,平均情況為O(log?(m+n))。
方法二:雙指針
思路及算法:
方法一沒有利用數(shù)組nums1與nums2已經(jīng)被排序的性質(zhì)。為了利用這一性質(zhì),我們可以使用雙指針方法。這一方法將兩個數(shù)組看作隊列,每次從兩個數(shù)組頭部取出比較小的數(shù)字放到結(jié)果中。如下面的動畫所示:
我們?yōu)閮蓚€數(shù)組分別設(shè)置一個指針p1?與p2?來作為隊列的頭部指針。
代碼實現(xiàn):
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int p1 = 0, p2 = 0;int sorted[m + n];int cur;while (p1 < m || p2 < n) {if (p1 == m) {cur = nums2[p2++];} else if (p2 == n) {cur = nums1[p1++];} else if (nums1[p1] < nums2[p2]) {cur = nums1[p1++];} else {cur = nums2[p2++];}sorted[p1 + p2 - 1] = cur;}for (int i = 0; i != m + n; ++i) {nums1[i] = sorted[i];}
}
復雜度分析
- 時間復雜度:O(m+n)。 指針移動單調(diào)遞增,最多移動m+n次,因此時間復雜度為O(m+n)。
- 空間復雜度:O(m+n)。 需要建立長度為m+n的中間數(shù)組sorted。
方法三:逆向雙指針
思路及算法:
方法二中,之所以要使用臨時變量,是因為如果直接合并到數(shù)組nums1中,nums1中的元素可能會在取出之前被覆蓋。那么如何直接避免覆蓋nums1中的元素呢?觀察可知,nums1的后半部分是空的,可以直接覆蓋而不會影響結(jié)果。因此可以指針設(shè)置為從后向前遍歷,每次取兩者之中的較大者放進nums1的最后面。
嚴格來說,在此遍歷過程中的任意一個時刻,nums1數(shù)組中有m?p1?1個元素被放入nums1的后半部,nums2數(shù)組中有n?p2?1個元素被放入nums1的后半部,而在指針p1的后面,nums1數(shù)組有 m+n?p1?1個位置。由于
m+n?p1?1≥m?p1?1+n?p2?1等價于p2≥?1
永遠成立,因此p1后面的位置永遠足夠容納被插入的元素,不會產(chǎn)生p1的元素被覆蓋的情況。
代碼實現(xiàn):
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int p1 = m - 1, p2 = n - 1;int tail = m + n - 1;int cur;while (p1 >= 0 || p2 >= 0) {if (p1 == -1) {cur = nums2[p2--];} else if (p2 == -1) {cur = nums1[p1--];} else if (nums1[p1] > nums2[p2]) {cur = nums1[p1--];} else {cur = nums2[p2--];}nums1[tail--] = cur;}
}
復雜度分析
- 時間復雜度:O(m+n)。 指針移動單調(diào)遞減,最多移動m+n次,因此時間復雜度為 O(m+n)。
- 空間復雜度:O(1)。 直接對數(shù)組nums1原地修改,不需要額外空間。