88. 合并兩個有序數(shù)組
題目描述
? ? 給你兩個按 非遞減順序 排列的整數(shù)數(shù)組 nums1 和 nums2，另有兩個整數(shù) m 和 n ，分別表示 nums1 和 nums2 中的元素數(shù)目。請你 合并 nums2 到 nums1 中，使合并后的數(shù)組同樣按 非遞減順序 排列。
注意：最終，合并后數(shù)組不應(yīng)由函數(shù)返回，而是存儲在數(shù)組 nums1 中。為了應(yīng)對這種情況，nums1 的初始長度為 m + n，其中前 m 個元素表示應(yīng)合并的元素，后 n 個元素為 0 ，應(yīng)忽略。nums2 的長度為 n 。
示例 1:
輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
解釋：需要合并 [1,2,3] 和 [2,5,6] 。
合并結(jié)果是 [1,2,2,3,5,6] ，其中斜體加粗標(biāo)注的為 nums1 中的元素。
示例 2:
輸入：nums1 = [1], m = 1, nums2 = [], n = 0
輸出：[1]
解釋：需要合并 [1] 和 [] 。
合并結(jié)果是 [1] 。
示例 3:
輸入：nums1 = [0], m = 0, nums2 = [1], n = 1
輸出：[1]
解釋：需要合并的數(shù)組是 [] 和 [1] 。
合并結(jié)果是 [1] 。
注意，因為 m = 0 ，所以 nums1 中沒有元素。nums1 中僅存的 0 僅僅是為了確保合并結(jié)果可以順利存放到 nums1 中。文章來源：http://www.zghlxwxcb.cn/news/detail-693887.html
分析：首先，由題目合并后數(shù)組不應(yīng)由函數(shù)返回，而是存儲在數(shù)組 nums1 中；定義m1，n1變量分別遍歷nums1和nums2，定義tail游標(biāo)，從后往前比較，且遍歷游標(biāo)不能越界，將較大者存入num1末尾。文章來源地址http://www.zghlxwxcb.cn/news/detail-693887.html
public class Solution {
public static void merge(int[] nums1, int m, int[] nums2, int n) {
int tail = nums1.length - 1;
int m1 = m - 1;
int n1 = n - 1;
while (n1 >= 0) {
if (m1 < 0 || nums1[m1] <= nums2[n1]) {
nums1[tail--] = nums2[n1--];
} else {
nums1[tail--] = nums1[m1--];
}
}
}到了這里，關(guān)于LeetCode面試算法-力扣 88. 合并兩個有序數(shù)組的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
