【Leetcode資料結構演算法題】合并兩個有序陣列（順序表篇）

題目內容：

給你兩個按 非遞減順序 排列的整數陣列 nums1 和 nums2，另有兩個整數 m 和 n ，分別表示 nums1 和 nums2中的元素數目， 請你 合并 nums2 到 nums1 中，使合并后的陣列同樣按 非遞減順序 排列，
注意：最終合并后陣列不應由函式回傳，而是存盤在陣列 nums1 中，為了應對這種情況，nums1 的初始長度為 m + n，其中前 m個元素表示應合并的元素，后 n 個元素為 0 ，應忽略，nums2 的長度為 n ，

leetcode題目鏈接（點擊即可跳轉）：

思路分析

看完題目，我們先別火急火燎的去編程做題，而是要先仔細理解題目的意思，（某些同學這時候可能會說“不是吧，不是吧，題目內容都給出來了，不會還有人看不懂吧？不會吧，不會吧！”）實際上，可能很多小伙伴們剛上手OJ題時（online judge 在線編程題)都不會很認真去審題，而是直接編程，然后報出一大堆錯誤，一個個除錯，最后，，，就沒有最后了，真的是“從入門到放棄~”，因此，為了避免這個問題，更加高效和正確的練習，我們應該要“理解題目—思路分析（畫圖理解）—極端場景—動手編程—回顧總結”，這些步驟看起來好像挺繁瑣的，但是實際上花的時間比直接上手編程還要少，而且最終的學習、練習效果也要好上不少，

（當然，分享博客也可以幫助我們梳理做題的思路，總結做題的經驗和方法，最最最重要的是能幫助到其他人，然刷題的這個程序多了一些“其他的意義”）

那么問題來了，如何更好的理解題目呢？
（1）將題目看完后，用自己的話復述出來，只需要大概的意思相同即可，

比如說這道題目，題目大概的意思就是“有兩個整體而言升序（就是中間可能存在相等的元素，不是嚴格升序，這就是對”非遞減排列“的理解）的陣列num1，num2，num1有m個元素，但是長度為m+n，num2有n個元素，長度為n，現在要求我們將兩個陣列合并成一個陣列并存放到num1當中，排序方式跟之前一樣，”

（2）從多個角度給自己提問

比如說：
①題目有要求說不能開辟臨時陣列嗎？或者說要求空間復雜度為O(1)，又或者是原地處理資料，（顯然本題是沒有這個要求的！）
②題目中有說m、n不能等于0嗎？如果等于0時該怎么處理？
③題目中對時間復雜度有要求嗎？（進階部分要求時間復雜度為O(n+m)

方法一：臨時陣列法

既然題目中沒有要求“原地”合并資料，那么我們應該很容易想到建立一個長度為n+m的臨時陣列，先將num1，num2兩個陣列中的內容按照“不降序”方式放到臨時陣列中，然后將臨時陣列中的內容拷貝回num1陣列中，
這種方式對于題目②出現的情況：

1）m=0、n=0 不符合題目提示中 1 <=
m+n的情況，（其實我還有點好奇如果真遇到了，m=n=0，m+n=0，怎么處理，能創建長度為0的臨時陣列嗎？長度為0的陣列有意義嗎？m=0時只是代表num1中沒有有效元素，但是實際的長度不為m，而是n+m >=1，如果真遇到了，都不用開辟臨時陣列，直接處理即可）
2）m=0、n>0，也就是說num1中無有效元素，num2中有n個有效元素，這個時候就會將num2中的資料先全部放到臨時陣列中，然后從陣列中拷貝到num1中，可以解決問題，不會出現錯誤（雖然效率有點低，但好歹解決問題了，問題不大）
3）n=0、m>0，也就是說num2中無有效元素，num1中有m個有效元素，這個時候就會將num1中的資料先全部放到臨時陣列中，然后從陣列中拷貝到num1中，可以解決問題，不會出現錯誤，（額，看起來呆呆的）

所以整體來看，臨時陣列的方式不會出現太大的問題，這個時候就可以畫出圖解，撰寫代碼測驗了，

演算法圖解

函式介面實作

void merge(int* nums1, int nums1Size, int m, 
int* nums2, int nums2Size, int n){
    int* arr = (int*)malloc((m+n)*sizeof(int));//創建長度為m+n的臨時變數
    int src1 = 0;//nums1的起始下標
    int src2 = 0;//nums2的起始下標
    int dest = 0;//arr的起始下標
    while((src1 < m) && (src2 < n)){
        if(nums1[src1] <= nums2[src2]){
            //將nums1的元素賦給arr，兩個陣列下標同時向后移動
            arr[dest++] = nums1[src1++];
        }
        else{
            //將nums2的元素賦給arr，兩個陣列下標同時向后移動
            arr[dest++] = nums2[src2++];
        }
    }
    //走到這里，表示num1或num2有一個已經結束了
    if(src1 == m){
        //src1 = m表示num1中的有效元素全部移到arr中了
        //只需要將num2中的元素全部移到arr中即可
        while(src2 < n){
            arr[dest++] = nums2[src2++];
        }
    }
    else{
        //src2 = n表示num2中的有效元素全部移到arr中了
        //只需要將num1中的元素全部移到arr中即可
        while(src1 < m){
            arr[dest++] = nums1[src1++];
        }
    }
    //最后將arr中的元素拷貝給num1
    for(int i = 0; i < (n+m); i++){
        nums1[i] = arr[i];
    }
    //釋放動態開辟的陣列
    free(arr);
    arr = NULL;
}

上述的這種使用臨時陣列的方法，我們再將num1、num2中的元素移到臨時陣列時，采用了從num1、num2兩個陣列的起始端到終止端的方式，也就是說采用了“從前往后”的方式，那么我們可不可以采用”從后往前“的方式呢？（既然我都問了，那我自然就不能”光說不做假把戲“）

方法二：臨時陣列倒立版

（別問為什么叫倒立版，為什么不叫翻轉版、逆序版、反向版？？？問就是我感覺”倒立版”三個字比較“霸氣”，對，就是比較“霸氣”，有木有一種“霸氣外露”的感覺？）
這種方法只需要在原來臨時陣列法的基礎上進行一些調整即可，主要是將src1、src2兩個下標從之前的“從前往后”遍歷變成“從后往前”遍歷，那么兩者比較的時候，就是誰大，誰就保留到臨時陣列arr中，注意臨時陣列也需要從后往前遍歷，

演算法圖解

函式介面實作

void merge(int* nums1, int nums1Size, int m, 
int* nums2, int nums2Size, int n){
    int* arr = (int*)malloc((m+n)*sizeof(int));//創建長度為m+n的臨時變數
    int src1 = m - 1;//nums1的終止下標
    int src2 = n - 1;//nums2的終止下標
    int dest = m + n - 1;//arr的終止下標
    while((src1 >= 0) && (src2 >= 0)){
        if(nums1[src1] >= nums2[src2]){
            //將nums1的元素賦給arr，兩個陣列下標同時向前移動
            arr[dest--] = nums1[src1--];
        }
        else{
            //將nums2的元素賦給arr，兩個陣列下標同時向前移動
            arr[dest--] = nums2[src2--];
        }
    }
    //走到這里，表示num1或num2有一個已經結束了
    if(src1 < 0){
        //src1 < 0表示num1中的有效元素全部移到arr中了
        //只需要將num2中的元素全部移到arr中即可
        while(src2 >= 0){
            arr[dest--] = nums2[src2--];
        }
    }
    else{
        //src2 < 0表示num2中的有效元素全部移到arr中了
        //只需要將num1中的元素全部移到arr中即可
        while(src1 >= 0){
            arr[dest--] = nums1[src1--];
        }
    }
    //最后將arr中的元素拷貝給num1
    for(int i = 0; i < (n+m); i++){
        nums1[i] = arr[i];
    }
    //釋放動態開辟的陣列
    free(arr);
    arr = NULL;
}

使用臨時陣列的方法，雖然可以解決問題，但是我們假設出現這樣一種情況“需要合并的兩個陣列很大，也就是m+n很大”，那么我們需要創建的臨時陣列的空間就越大，空間復雜度為O(n+m)，上面的兩種臨時陣列方法時間復雜度都是O(n+m)，也就是說符合進階版的要求，
時間復雜度、空間復雜度相關文章：
【資料結構學習筆記】一、資料結構介紹及演算法分析（新手入門進階指南）
那么有沒有一種方法既可以不開辟臨時陣列，又可以達到類似臨時陣列的效果呢？（也就是說時間復雜度不變，為O(n+m)，但是空間復雜度變成了O(1))
答案當然是“有！”，這種方法我愿稱之為“超級進階版，豪華進階版，終極plus版”，至少目前我還找不到比這種方法還高效的演算法了，

方法三：虛擬陣列法（超級豪華終極puls版）

這種方法可以說是從“臨時陣列倒立版”發展而來（至少我是這么想到的），倒立版中兩個陣列從后往前遍歷將較大的數保存到臨時陣列中，實際上可以不用放到臨時陣列里面，而是可以直接放到num1里面，因為num1本身的長度是夠了（m+n）且num1后面的n個位置是不放有效資料的，不用擔心資料被覆寫掉，（如果你要從前往后遍歷就需要擔心將原來num1中的資料給覆寫了）最后將臨時陣列內容拷貝回num1中的這一步可以省略，（此處應該有“666、Nb、我滴天啦！”）

演算法圖解

函式介面實作

void merge(int* nums1, int nums1Size, int m, 
int* nums2, int nums2Size, int n){
    int src1 = m - 1;//陣列nums1有效元素的終止下標
    int src2 = n - 1;//陣列nums2的終止下標
    int dest = m + n - 1;//陣列nums1整體的終止下標
    while(src1 >= 0 && src2 >=0){
        if(nums1[src1] >= nums2[src2]){
            //將nums1的src1指向的元素賦給nums1的dest指向的位置
            //兩個陣列下標同時向前移動
            nums1[dest--] = nums1[src1--];
        }
        else{
            //將nums2的src2指向的元素賦給nums1的dest指向的位置
            //兩個陣列下標同時向前移動
            nums1[dest--] = nums2[src2--];
        }
    }
    //走到這里代表src1或src2走完了
    if(src1 < 0){
        //如果是src1提前走完，將nums2中元素全部拷貝給nums1
        while(src2 >= 0){
            nums1[dest--] = nums2[src2--];
        }
    }
    //如果是src2提前走完，不需要進行任何處理
}

原創不易，各位小伙伴點個贊，評個論，光個注唄~
你們的支持將是我前進的最大動力！！！