題目描述：

給你兩個按 非遞減順序 排列的整數(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 。

解法：雙數(shù)組的雙指針遍歷

算法思路分析：

整體過程分三步：

• 開一個 m + n 的數(shù)組，合并兩個有序數(shù)組到新開辟的數(shù)組內(nèi)，然后將新開辟的數(shù)組拷貝到原數(shù)組中。主要的難點就是如何合并兩個有序數(shù)組。
• 由于兩個數(shù)組都是非遞減的，因此兩個數(shù)組的首元素一定是它們所處的數(shù)組的最小值。那么，我們每一次合并的時候，僅需比較兩個數(shù)組的首元素，誰最小，誰就是當前所有元素中最小的元素。
• 然后將最小的元素添加到開辟的數(shù)組中，并且把最小的元素從原數(shù)組中去掉就可以了。

算法流程：

• 開辟一個大小為** m + n** 的數(shù)組 ret。
• 初始化三個指針，cur1 = 0, cur2 = 0, dest = 0 分別指向 nums1，nums2，ret 的首元素。
• 當 cur1 < m 并且 cur2 < n 時，一直循環(huán)下述過程：
• （思考結(jié)束條件：因為我們每次只取出某一個數(shù)組中的一個元素，因此，一定有一個數(shù)組會先被遍歷完，而此時剩下的一個數(shù)組的內(nèi)容，我們只用原封不動的拷貝到 ret 數(shù)組中即可。因此，結(jié)束條件就是 cur1 或者 cur2 任意一個指針遍歷到數(shù)組結(jié)束位置）
• 比較 nums1[cur1] 與 nums2[cur2] 的大小，分為下面三種：
• nums1[cur1] < nums2[cur2]；說明 nums1[cur1] 是最小的元素，將其放到 ret 數(shù)組中，并且讓 cur1++（相當于去掉當前元素），dest++（指向下一個元素的位置），因此可以這樣寫：ret[dest++] = nums1[cur1++]；
• nums1[cur1] = nums2[cur2]；因為此時兩個數(shù)相等，我們讓其中任意一個元素加入到** ret** 數(shù)組中均可，因此可以并到上述情況中；
• nums1[cur1] > nums2[cur2]；說明** nums2[cur2]** 是最小的元素，同理可得 ret[dest++] = nums2[cur2++]；
• 處理沒有遍歷完的數(shù)組
• 將沒有遍歷完的數(shù)組全部拷貝到 ret 數(shù)組中即可
• 不要忘記將 ret 數(shù)組的內(nèi)容再拷貝到原數(shù)組中去

最后整理代碼為：

#include <stdio.h>
#include <stdlib.h>void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{// 開辟一個新數(shù)組，用來存放合并后的結(jié)果int* ret = (int*)malloc(sizeof(int) * (m + n));// 初始化三個指針，用來遍歷三個數(shù)組int cur1 = 0, cur2 = 0, dest = 0;// 當其中一個遍歷到數(shù)組的結(jié)尾，我們就結(jié)束循環(huán)while (cur1 < m && cur2 < n){// 當?shù)谝粋€數(shù)組的元素比較小的時候，我們就加入合并后的數(shù)組if (nums1[cur1] <= nums2[cur2])ret[dest++] = nums1[cur1++];// 否則就將第二個元素加入到目標數(shù)組elseret[dest++] = nums2[cur2++];}// 下面兩個循環(huán)只會執(zhí)行一個，因為只會有一個數(shù)組還有剩余元素// 當?shù)谝粋€數(shù)組的元素有剩余的話，就會執(zhí)行第一個循環(huán)while (cur1 < m)ret[dest++] = nums1[cur1++]; // 將數(shù)組的內(nèi)容拷貝到合并后的數(shù)組中// 當?shù)诙€數(shù)組的元素有剩余的話，就會執(zhí)行第二個循環(huán)while (cur2 < n)ret[dest++] = nums2[cur2++];// 將合并后的數(shù)組，放回第一個數(shù)組中去for (int i = 0; i < m + n; i++){nums1[i] = ret[i];}// 釋放輔助數(shù)組free(ret);
}