目錄

題目描述

思路分析

我的題解

題目描述

給你兩個按 非遞減順序 排列的整數(shù)數(shù)組?nums1 和 nums2，另有兩個整數(shù) m 和 n ，分別表示 nums1 和 nums2 中的元素數(shù)目。

請你 合并 nums2 到 nums1 中，使合并后的數(shù)組同樣按 非遞減順序 排列。

注意：最終，合并后數(shù)組不應由函數(shù)返回，而是存儲在數(shù)組 nums1 中。為了應對這種情況，nums1 的初始長度為 m + n，其中前 m 個元素表示應合并的元素，后 n 個元素為 0 ，應忽略。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
?

進階：你可以設計實現(xiàn)一個時間復雜度為 O(m + n) 的算法解決此問題嗎？

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/merge-sorted-array
著作權(quán)歸領(lǐng)扣網(wǎng)絡所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

思路分析

思路1：

? ? ? ? 最簡單粗暴的方法就是先將nums2的所有元素插入到nums1的后面，然后用C\C++內(nèi)置的qsort\sort函數(shù)對其進行排序。當然這個方法并不是一個很好的解法。

思路2：

? ? ? ? 我們可以考慮借助一個額外的數(shù)組來實現(xiàn)排序。首先需要兩個指針i，j來控制兩數(shù)組的下標。然后nums1和nums2從頭開始將較小值放入到這個額外的數(shù)組中。特別的，如果其中一個數(shù)組的指針走到了最后，就直接將另一個數(shù)組的內(nèi)容放入到額外的數(shù)組中。

思路3：

? ? ? ? 雖然感覺思路2已經(jīng)可以了，但還是差點意思，就是是否可以不使用額外的空間呢？答案是可以的。由于思路2的nums1和nums2是從頭開始的，為了防止與nums1的內(nèi)容沖突所以需要一個額外的數(shù)組，那么我們可以從后開始，因為nums1的最后是沒有數(shù)據(jù)的，所以我們可以從后開始，不斷將兩數(shù)組i，j位置兩數(shù)的較大值放入nums1的i+j+2的位置（至于為什么是這個等式，畫圖看一下就會豁然開朗）。

我的題解

思路3的代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-414569.html

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    int i = m - 1, j = n - 1; //i是nums1的下標，j是nums2的下標
    int value = 0; 
    while ( i + j + 1 >= 0) 
    {
        if(i == -1)
        {
             value = nums2[j--];
        }
        else if(j == -1)
        {
            value = nums1[i--]; 
        }
        else
            value = nums1[i] >= nums2[j] ? nums1[i--] : nums2[j--];
        nums1[i + j + 2] = value;
    }
}

到了這里，關(guān)于LeetCode_88. 合并兩個有序數(shù)組的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！