• 🎈個人主頁：庫庫的里昂
• ?🎐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原地修改，不需要額外空間。