力扣網(wǎng) 88. 合并兩個(gè)有序數(shù)組
題目描述
給你兩個(gè)按?非遞減順序?排列的整數(shù)數(shù)組?nums1?和?nums2，另有兩個(gè)整數(shù)?m?和?n?，分別表示?nums1?和?nums2?中的元素?cái)?shù)目。
請(qǐng)你?合并?nums2?到?nums1?中，使合并后的數(shù)組同樣按?非遞減順序?排列。
注意：最終，合并后數(shù)組不應(yīng)由函數(shù)返回，而是存儲(chǔ)在數(shù)組?nums1?中。為了應(yīng)對(duì)這種情況，nums1?的初始長(zhǎng)度為?m + n，其中前?m?個(gè)元素表示應(yīng)合并的元素，后?n?個(gè)元素為?0?，應(yīng)忽略。nums2?的長(zhǎng)度為?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] 。 注意，因?yàn)?m = 0 ，所以 nums1 中沒(méi)有元素。nums1 中僅存的 0 僅僅是為了確保合并結(jié)果可以順利存放到 nums1 中。
思路分析
方法1
時(shí)間復(fù)雜度? O（m+n）
空間復(fù)制度 O（m+n）
這是最基本的思路，將兩個(gè)數(shù)組從頭遍歷，分別比較大小，較小的值先放到一個(gè)新創(chuàng)建的數(shù)組里，比較完后可能會(huì)存在剩余的情況，再將剩余的值放入新數(shù)組，題目要求返回?cái)?shù)組1，再將新數(shù)組的內(nèi)容拷貝進(jìn)數(shù)組1里即可
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int s1=0;
int s2=0;
int num3[200]={0};//新數(shù)組
int i=0;
while(s1<m&&s2<n)//任何一個(gè)數(shù)組遍歷完結(jié)束循環(huán)
{
if(nums1[s1]<nums2[s2])//較小值先放
{
num3[i++]=nums1[s1++];
}
else if(nums1[s1]==nums2[s2])//相等則一起放，任意規(guī)則
{
num3[i++]=nums1[s1++];
num3[i++]=nums2[s2++];
}
else
{
num3[i++]=nums2[s2++];
}
}
if(s1==m)//s1遍歷完的情況下，s2還沒(méi)有遍歷完的情況下
{
while(s2<n)
{
num3[i++]=nums2[s2++];
}
}
if(s2==n)//s2遍歷完的情況下，s1還沒(méi)有遍歷完
{
while(s1<m)
{
num3[i++]=nums1[s1++];
}
}
for(int j=0;j<nums1Size;j++)//將新數(shù)組拷貝到數(shù)組1里
{
nums1[j]=num3[j];
}
}方法2
時(shí)間復(fù)雜度? O（m+n）
空間復(fù)雜度? O（1）
思路：從兩個(gè)數(shù)組的末尾開(kāi)始遍歷，數(shù)組1從最后一個(gè)數(shù)開(kāi)始向前遍歷，較大值放到數(shù)組1的末尾，如果遍歷完數(shù)組2還有剩余的話直接放入。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-714615.html
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int s1=m-1;//數(shù)組1的末尾（最后一個(gè)數(shù)字）
int s2=n-1;//數(shù)組2的末尾
int index=m+n-1;//（數(shù)組1的末尾）
while(s1>=0&&s2>=0)
{
if(nums1[s1]>nums2[s2])
{
nums1[index--]=nums1[s1--];
}
else
{
nums1[index--]=nums2[s2--];
}
}
while(s2>=0)//數(shù)組2還有剩余的情況
{
nums1[index--]=nums2[s2--];
}
}?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-714615.html
到了這里，關(guān)于C語(yǔ)言每日一題（22）合并兩個(gè)有序數(shù)組的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
