每日一道 LeetCode (19)：合并兩個(gè)有序數(shù)組
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉庫
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：合并兩個(gè)有序數(shù)組
題目來源：https://leetcode-cn.com/problems/merge-sorted-array/
給你兩個(gè)有序整數(shù)數(shù)組 nums1 和 nums2，請你將 nums2 合并到 nums1 中，使 nums1 成為一個(gè)有序數(shù)組。
說明:
初始化 nums1 和 nums2 的元素?cái)?shù)量分別為 m 和 n 。
你可以假設(shè) nums1 有足夠的空間（空間大小大于或等于 m + n）來保存 nums2 中的元素。
示例:
輸入:
nums1?=?[1,2,3,0,0,0],?m?=?3
nums2?=?[2,5,6],???????n?=?3
輸出:?[1,2,2,3,5,6]
解題方案
這道題單純的從排序上來講并不是難題，畢竟題目中已經(jīng)給出來兩個(gè)有序的數(shù)組了，最簡單的循環(huán)一下長數(shù)組，然后挨個(gè)比較下兩個(gè)數(shù)組元素的大小，放到一個(gè)新數(shù)組里面就完事兒了。
這道題的難點(diǎn)在于，我們需要在 nums1 數(shù)組中，完成兩個(gè)數(shù)組的排序，這個(gè)就稍微有點(diǎn)坑了，這相當(dāng)于要把 nums2 合并到 nums1 當(dāng)中，還得要有序的合并進(jìn)去。
這個(gè)彎有點(diǎn)難繞的，題目中雖然說最終的結(jié)果要在 nums1 當(dāng)中，但是并沒有說不允許我們創(chuàng)建第三個(gè)數(shù)組啊，我可以創(chuàng)建一個(gè)新的數(shù)組，把 nums1 copy 到新的數(shù)組中，然后再在 nums1 當(dāng)中完成排序，這不也行么。
接下來就是代碼時(shí)間，很簡單，定義了兩個(gè)指針，一個(gè)是 copy_nums1 的指針，還有一個(gè)是 nums2 的指針，通過移動這兩個(gè)指針，來完成整個(gè)排序工作。
//?從前往后
public?void?merge(int[]?nums1,?int?m,?int[]?nums2,?int?n)?{
????int[]?copy_nums1?=?new?int[m];
????System.arraycopy(nums1,?0,?copy_nums1,?0,?m);
????//?copy_nums1?的指針
????int?n1?=?0;
????//?nums2?的指針
????int?n2?=?0;
????//?nums1?的指針
????int?n0?=?0;
????while?((n1?????????nums1[n0++]?=?copy_nums1[n1]?????}
????if?(n1?????????System.arraycopy(copy_nums1,?n1,?nums1,?n1?+?n2,?m?+?n?-?n1?-?n2);
????}
????if?(n2?????????System.arraycopy(nums2,?n2,?nums1,?n1?+?n2,?m?+?n?-?n1?-?n2);
????}
}
上面這種方案雖說能解決問題，但是有一點(diǎn)不大好，就是新建了一個(gè)數(shù)組，多占用了一個(gè)數(shù)組的空間，既然題上說 nums1 的長度足夠上，我們從小到大排序不好排，那么如果是從大到小呢？
思路基本上還是一個(gè)思路，定義兩個(gè)指針，然后倒序的將元素裝到 nums1 里面。
//?從后往前
public?void?merge_1(int[]?nums1,?int?m,?int[]?nums2,?int?n)?{
????//?nums1?有數(shù)據(jù)的尾部指針
????int?n1?=?m?-?1;
????//?nums2?的尾部指針
????int?n2?=?n?-?1;
????//?nums1?最終的尾部指針
????int?n0?=?m?+?n?-?1;
????while?((n1?>=?0)?&&?(n2?>=?0))?{
????????nums1[n0--]?=?nums1[n1]?????}
????System.arraycopy(nums2,?0,?nums1,?0,?n2?+?1);
}
今天這兩道題都不難，基本上搞清楚了方案以后，就是寫寫代碼練練手。
