目錄
題目：
示例：
分析：
代碼：
題目：
示例：
分析：
題目給我們兩個升序數(shù)組，讓我們合并它們，要求合并之后仍然是升序，并且這個合并操作是在數(shù)組1原地修改的。數(shù)組1的有效數(shù)據(jù)長度為 m ，而數(shù)組1的長度為 m + n，n 是數(shù)組2的有效數(shù)據(jù)長度以及數(shù)組的長度。
比較直觀容易想到的做法就是先把數(shù)組1的尾部刪去 n 個無效數(shù)據(jù)，再把數(shù)組2都添加到數(shù)組1的尾部。接著直接對數(shù)組1排序即可。這樣做是可以的，效果也還不錯。
?不過這么做就沒有利用到原數(shù)組是升序的這樣一個特性。
另一個容易想到的是雙指針，我們用雙指針遍歷分別兩個數(shù)組，每次都比較兩個指針?biāo)冈氐拇笮?，將較小的元素添加進新數(shù)據(jù)，接著往后移動該指針。直到兩個指針的大小分別為 m 和 n 即為遍歷結(jié)束。
最后將新數(shù)組賦值給數(shù)組1即可。
那這么做還是有點不痛快，還是直接在數(shù)組1原地修改比較舒服。那有沒有辦法呢？
答案是有的。
首先我們上述辦法肯定是不行的，這么做會把數(shù)組1的有效數(shù)據(jù)覆蓋掉，那應(yīng)該怎么做呢。
我們覆蓋無效數(shù)據(jù)不就好啦，不能從頭遍歷我們就從尾部遍歷，一樣是雙指針，只不過兩個指針初始化為 m - 1 和 n - 1 ，每次比較兩個指針?biāo)冈氐拇笮?，我們把較大的元素放到數(shù)組1的末尾，直到兩個指針都小于0，那么我們就是原地合并兩個數(shù)組完畢了。文章來源：http://www.zghlxwxcb.cn/news/detail-651196.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-651196.html
代碼：
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int index1=m-1,index2=n-1,index3=n+m-1;
while(index1>=0&&index2>=0){
if(nums1[index1]>nums2[index2]) nums1[index3--]=nums1[index1--];
else nums1[index3--]=nums2[index2--];
}
while(index1>=0) nums1[index3--]=nums1[index1--];
while(index2>=0) nums1[index3--]=nums2[index2--];
}
};到了這里，關(guān)于【力扣每日一題】2023.8.13 合并兩個有序數(shù)組的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
