題目
給你兩個按 非遞減順序 排列的整數(shù)數(shù)組 nums1 和 nums2，另有兩個整數(shù) m 和 n ，分別表示 nums1 和 nums2 中的元素數(shù)目。
請你 合并 nums2 到 nums1 中，使合并后的數(shù)組同樣按 非遞減順序 排列。文章來源：http://www.zghlxwxcb.cn/news/detail-810400.html
注意：最終，合并后數(shù)組不應(yīng)由函數(shù)返回，而是存儲在數(shù)組 nums1 中。為了應(yīng)對這種情況，nums1 的初始長度為 m + n，其中前 m 個元素表示應(yīng)合并的元素，后 n 個元素為 0 ，應(yīng)忽略。nums2 的長度為 n 。文章來源地址http://www.zghlxwxcb.cn/news/detail-810400.html
思路
- 雙指針
- 新建一個數(shù)組，以及兩個指針，分別指向 n u m s 1 , n u m s 2 nums1, nums2 nums1,nums2 起始位置
- 比較 n u m s 1 [ p 1 ] nums1[p1] nums1[p1] 和 n u m s 2 [ p 2 ] nums2[p2] nums2[p2] 將小的放入新建的數(shù)組中，并將指針加 1 1 1
- 把新建的數(shù)組賦給 n u m s 1 nums1 nums1
- 降低空間復(fù)雜度
- 倒序比較可以防止覆蓋
- 初始化三個指針： p 1 = m ? 1 , p 2 = n ? 1 , p = m + n ? 1 p1=m-1, p2=n-1,p=m+n-1 p1=m?1,p2=n?1,p=m+n?1
- 比較 n u m s 1 [ p 1 ] nums1[p1] nums1[p1] 和 n u m s 2 [ p 2 ] nums2[p2] nums2[p2] 將大的放入 n u m s [ p ] nums[p] nums[p]，并將指針減 1 1 1
代碼
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1;
int p2 = n - 1;
int p = m + n - 1;
while(p >= 0){
if(p1 == -1){
nums1[p] = nums2[p2];
p--;
p2--;
}
else if(p2 == -1){
nums1[p] = nums1[p1];
p--;
p1--;
}
else if(nums1[p1] > nums2[p2]){
nums1[p] = nums1[p1];
p--;
p1--;
}
else{
nums1[p] = nums2[p2];
p--;
p2--;
}
}
}
};
到了這里，關(guān)于力扣_數(shù)組26—合并兩個有序數(shù)組的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
