各位CSDN的uu們你們好呀，又到小雅蘭的愉快題解時(shí)候啦，今天，我們的題目?jī)?nèi)容是合并兩個(gè)有序數(shù)組，下面，讓我們進(jìn)入合并兩個(gè)有序數(shù)組的世界吧
示例 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] 。
注意，因?yàn)?m = 0 ，所以 nums1 中沒有元素。nums1 中僅存的 0 僅僅是為了確保合并結(jié)果可以順利存放到 nums1 中。
?
方法一：直接合并后排序
?最直觀的方法是先將數(shù)組nums2放進(jìn)數(shù)組nums1的尾部，然后直接對(duì)整個(gè)數(shù)組進(jìn)行排序。
int cmp(int* a, int* b) {
return *a - *b;
}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
for (int i = 0; i != n; ++i) {
nums1[m + i] = nums2[i];
}
qsort(nums1, nums1Size, sizeof(int), cmp);
}但是這種方法不太好，來看看另外一種方法：?
方法二：雙指針法
?
這種方法就比較好了
但是這種方法有點(diǎn)問題：如果第二個(gè)數(shù)組的首元素是0的話，依次比較，取小的尾插，那么就會(huì)覆蓋，所以換一種方式
倒著比?。。∫簿褪菑暮笸氨?。
?
以此類推，這樣的方法也是非常高效的
下面，我們來看看源代碼：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int end1=m-1;
int end2=n-1;
int i=m+n-1;
while(end1>=0 && end2>=0)
{
if(nums1[end1]>nums2[end2])
{
nums1[i]=nums1[end1];
i--;
end1--;
}
else
{
nums1[i]=nums2[end2];
i--;
end2--;
}
}
while(end2>=0)
{
nums1[i]=nums2[end2];
i--;
end2--;
}
}
?
好啦，小雅蘭的今日題解分享就到這里啦，還要繼續(xù)加油刷題噢！??！
文章來源：http://www.zghlxwxcb.cn/news/detail-423380.html
?文章來源地址http://www.zghlxwxcb.cn/news/detail-423380.html
到了這里，關(guān)于Leetcode每日一題——“合并兩個(gè)有序數(shù)組”的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
