合併兩個有序數組
題目來源：力扣（LeetCode）
題目詳情：
給你兩個有序整數數組 nums1 和 nums2，請你將 nums2 合併到 nums1 中，使 nums1 成為一個有序數組。
說明:
初始化 nums1 和 nums2 的元素數量分別為 m 和 n 。
你可以假設 nums1 有足夠的空間（空間大小大於或等於 m + n）來保存 nums2 中的元素。
示例:
輸入:
nums1 = [1,8,9,15,0,0,0,0,0], m = 4
nums2 = [2,5,6,12,18], n = 5
輸出:
[1,2,5,6,8,9,12,15,18]
解法一：
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] result = new int[m+n]; // 創建一個大小為m+n的數組，確保裝的下所有排序的元素
int i = 0;
int j = 0;
int k = 0;
while(i < m && j < n){ // 從左往右，往result中裝數據
if(nums1[i] <= nums2[j]){
result[k++] = nums1[i++];
}else{
result[k++] = nums2[j++];
}
}
while(i < m){ // 將nums1中剩餘元素加到result後面
result[k++] = nums1[i++];
}
while(j < n){ // 將nums2中剩餘元素加到result後面
result[k++] = nums2[j++];
}
for(int s = 0; s < result.length; s++){ // 將排好序的result拷貝給nums1
nums1[s] = result[s];
}
}
}
這種解法很簡單，也很容易理解。就是額外創建一個數組result，數組的大小為m + n即所有排序元素的個數，用來往裏面從左到右、從小到大裝數據。創建三個指針，i 指向數組nums1的第一個元素，j 指向數組nums2的第一個元素，k 指向數組result的第一個位置。
比較nums1和nums2的指針所指向的當前元素的大小，小的填入到result中 k 指向的位置，此時兩個指針都向前移動一位，重複當前操作——填數據。
直到nums1和nums2其中一個數組遍歷完了，此時另一個未遍歷完的數組中剩餘的數都大於result中的元素，將這些數依次加到result後面。
到現在，我們得到了一個已經包含nums1和nums2中所有元素的排好序的數組result，但是還沒有結束，因為我們所要做的是合併兩個數組，也就是將nums2合併到nums1中，最後nums1是一個合併好的、排好序的數組，我們當前的nums1還不是。所以，我們還要更新一下nums1，將result中的元素拷貝到nums1中，至此nums1才是題目要求的樣子。
解法二：
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int len1 = m - 1;
int len2 = n - 1;
int len = m + n - 1;
while(len1 >= 0 && len2 >= 0) {
nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
}
// 將nums2數組從下標0位置開始，拷貝到nums1數組中，從下標0位置開始，長度為len2+1
System.arraycopy(nums2, 0, nums1, 0, len2 + 1);
}
}
這種方法相對巧妙一點，沒有額外的創建數組，減少了算法的空間複雜度。讓我們來看一看這種解法的思路是什麼吧。
解法一的思路是從小到大填數，以此相反，這種解法是從大到小填數據，是在數組nums1上從後往前填數，選擇大的填。
while循環中，當數組nums2中的元素都被填完後，nums1就排好序了；當nums1中的元素被填完，而nums2中的元素還有一些時，語句 System.arraycopy(nums2, 0, nums1, 0, len2 + 1); 就發揮作用了，會將nums2中剩餘的元素加到nums1中，使得nums1合併排序完成。
