一、題目描述

給你兩個(gè)有序整數(shù)數(shù)組nums1和nums2，請(qǐng)你將nums2合并到nums1中，使nums1成為一個(gè)有序數(shù)組。

初始化nums1和nums2的元素?cái)?shù)量分別為 m 和 n 。

你可以假設(shè)nums1的空間大小等于 m + n，這樣它就有足夠的空間保存來自nums2的元素。

二、題目解析

設(shè)置兩個(gè)索引i和j分別指向 nums1 和 nums2 的有效元素的尾部，從它們的尾部開始向前遍歷。

同時(shí)設(shè)置索引cur指向nums1的最末尾。

在每次遍歷過程中，比較i和j指向的元素值大小，把大的元素填充到cur的位置，填充完畢說明那個(gè)元素已經(jīng)放置在它應(yīng)該放置的位置，不需要在管它了，把cur向前移動(dòng)，同時(shí)把i或者j向前移動(dòng)。

繼續(xù)比較i和j指向的元素值大小，把大的元素填充到cur的位置。

三、參考代碼

classSolution{
publicvoidmerge(int[]nums1,intm,int[]nums2,intn){
//索引從有序數(shù)組nums1有效元素的末端開始
//數(shù)組的下標(biāo)索引從零開始計(jì)數(shù)
//索引012
//數(shù)組[1,2,3]
inti=m-1;

//索引從有序數(shù)組nums2的末端開始
intj=n-1;

//從有序數(shù)組nums1最末端的位置開始保存元素
intcur=nums1.length-1;

//通過循環(huán)把num2的元素都移動(dòng)到num1中
while(j>=0){

//比較num1和num2中當(dāng)前的元素大小

//如果num1中的索引位置為i的元素大于num2中索引位置為j的元素
//為了防止越界i必須是大于等于0
if(i>=0&&nums1[i]>nums2[j]){

//把num1中的索引位置為i的元素復(fù)制到索引為cur的位置
//此時(shí)cur的元素已經(jīng)確定下來
nums1[cur]=nums1[i];

//接下來去確定cur前面一個(gè)元素應(yīng)該放什么數(shù)字
cur--;
//此時(shí)，索引i需要向前移動(dòng)
i--;
//否則，如果num1中的索引位置為i的元素小于或者等于num2中索引位置為j的元素
}else{

//把num2中的索引位置為j的元素復(fù)制到索引為cur的位置
nums1[cur]=nums2[j];
//接下來去確定cur前面一個(gè)元素應(yīng)該放什么數(shù)字
cur--;
//此時(shí)，索引j需要向前移動(dòng)
j--;
}
}
}
}

審核編輯 ：李倩