題目：
給你兩個有序整數陣列 nums1 和 nums2，請你將 nums2 合并到 nums1 中，使 nums1 成為一個有序陣列，
初始化 nums1 和 nums2 的元素數量分別為 m 和 n ，你可以假設 nums1 的空間大小等于 m + n，這樣它就有足夠的空間保存來自 nums2 的元素，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/merge-sorted-array
示例 1:
輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
示例 2:
輸入：nums1 = [1], m = 1, nums2 = [], n = 0
輸出：[1]
思路一：
將兩個陣列合并后排序，呼叫arraycopy()方法，將指定源陣列中的陣列從指定位置復制到目標陣列的指定位置，再使用sort()方法進行排序，
代碼演示：
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
//呼叫arraycopy()方法，從源陣列的0位置拷貝到目標陣列的m位置，拷貝n各元素
System.arraycopy(nums2, 0, nums1, m, n);
//呼叫陣列中的排序方法，對陣列進行排序
Arrays.sort(nums1);
}
檢查結果：
注釋：
這道題最容易想到的方法就是直接呼叫方法，只用了nums1和nums2的陣列，空間浪費資少，但是沒有使用有序條件，使得陣列一一取出重新排序，大大浪費了時間，
思路二：
思路一并沒有使用題目中使用的條件“有序”,源陣列按照了從小到大排序，利用有序，可以使用雙指標，兩個陣列，從頭部取出比較小的數字放在結果中，設立一個p1和p2作為頭部指標，移動獲取資料，
代碼演示：
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
//控制指標從0開始，
int p1 = 0, p2 = 0;
//創建一個新陣列存盤排序后的資料
int[] arr = new int[m + n];
//創建一個數比較較小值，此題為有序陣列
int min;
//回圈指標移動比較元素，通過指標自增自減控制指標移動
while (p1 < m || p2 < n) {
//如果指標到最后一位，另一個陣列的元素進入新陣列
if (p1 == m) {
min = nums2[p2++];
} else if (p2 == n) {
min = nums1[p1++];
} else if (nums1[p1] < nums2[p2]) {
min = nums1[p1++];
} else {
min = nums2[p2++];
}
//將較小的值存盤進新陣列里
arr[p1 + p2 - 1] = min;
}
for (int i = 0; i != m + n; ++i) {
nums1[i] = arr[i];
}
}
}
檢查結果：
注釋：
思路二使用了雙指標，從頭到尾一一取出元素，減少了對比的時間，使用了中間變數，如果直接合并到陣列nums1，nums1中元素可能在取出前被覆寫了，使用中間變數浪費了記憶體空間，
思路三：
如果直接合并到陣列nums1中，nums1元素有可能在取出是被覆寫，造成元素丟失，據觀察nums1的后半部分都是空的，可以直接覆寫不會影響結果，我們可以使用雙指標，從后向前遍歷，每次取兩者之間最大的值放入到陣列的最后，
代碼演示：
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
//倒序，從最后一個開始
int p1 = m - 1, p2 = n - 1;
//陣列長度
int length = m + n - 1;
int max;
while (p1 != -1 || p2 != -1) {
if (p1 == -1) {
max = nums2[p2--];
} else if (p2 == -1) {
max = nums1[p1--];
} else if (nums1[p1] > nums2[p2]) {
max = nums1[p1--];
} else {
max = nums2[p2--];
}
nums1[length--] = max;
}
}
}
檢查結果：
注釋：
此方法即使用題目中的“有序”，將兩個陣列元素一一對比取出，大大減少了對比的時間，又不用擔心nums1元素在取出前被覆寫的問題，還不需要使用中間變數，減少了記憶體的使用，
感謝你的閱讀，不足之處歡迎批評指正！
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/274773.html
標籤：其他
上一篇：【C語言初階】初識c語言
下一篇：程式員應該如何才能買房？