LeetCode 88. 合并兩個有序數(shù)組

思路1：暴力求解

1. 首先創(chuàng)建一個臨時數(shù)組，其大小為第一個數(shù)組的大?。磏ums1Size），其作用主要是。
2. 通過循環(huán)遍歷兩個數(shù)組，將兩個數(shù)組元素比較后較小的元素依次加入到臨時數(shù)組中，直到有一個數(shù)組遍歷完即可（注意：這里遍歷完是只有效元素被遍歷完，因為nums1中有無效元素0）。
3. 將未遍歷完的數(shù)組剩下的元素依次加入到臨時數(shù)組中。
4. 將臨時數(shù)組中的元素依次拷貝到nums1數(shù)組中。
5. 釋放臨時數(shù)組的空間。
   
   時間復(fù)雜度：O(m+n)
   空間復(fù)雜度：O(m+n)

值得注意的是： 這里需要考略到兩種特殊情況需要單獨處理

• nums2 數(shù)組為空時，nums1 數(shù)組就是兩個數(shù)組排序后的結(jié)果，函數(shù)不需要執(zhí)行任何操作，直接 return 即可
• nums1 數(shù)組中有效的元素個數(shù)為 0（即 m = 0 ） 時，此時 nums2 數(shù)組中的元素就是兩個數(shù)組排序后的結(jié)果，此時只需要將 nums2 中的數(shù)組元素拷貝到 nums1 數(shù)組即可。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    if(nums2==NULL)
    {
        return;
    }
    else if(m==0)
    {
        for(int i=0;i<nums1Size;i++)
        {
            nums1[i]=nums2[i];
        }
    }
    //創(chuàng)建一個數(shù)組來臨時存放排序之后的元素，元素個數(shù)為m+n = nums1Size
    int *arr = (int*)malloc((nums1Size)*sizeof(int));
    int index = 0,dest = 0,src = 0;
    //dest和src分別標(biāo)記訪問當(dāng)前數(shù)組元素的下標(biāo)
    //index標(biāo)記臨時數(shù)組加入元素的下標(biāo)位置
    //依次遍歷兩個數(shù)組，直到有一個數(shù)組遍歷完為止
    while(dest < m && src < n)
    {
        if(nums1[dest]<=nums2[src])
        {
            arr[index++] = nums1[dest++];
        }
        else
        {
            arr[index++] = nums2[src++];
        }
    }
    //將未遍歷完的數(shù)組剩下的元素加入到臨時數(shù)組中
    if(src>=n)
    {
        while(dest<m)
        {
            arr[index++] = nums1[dest++];
        }
    }
    else if(dest>=m)
    {
        while(src<n)
        {
            arr[index++] = nums2[src++];
        }
    }
    //將臨時數(shù)組中的元素依次賦值給nums1數(shù)組中對應(yīng)位置的元素
    for(int i = 0;i<nums1Size;i++)
    {
        nums1[i] = arr[i];
    }
    free(arr);//將創(chuàng)建的數(shù)組空間釋放
}

思路2：原地合并

1. 從后往前遍歷數(shù)組，將 nums1 和 nums2 中的元素逐個比較，將較大的元素往 nums1 末尾進(jìn)行搬移
2. 第一步結(jié)束后，nums2 中可能會有數(shù)據(jù)沒有搬移完，將 nums2 中剩余的元素逐個搬移到 nums1
3. 如果 num1 中剩余元素沒有搬移完，就不需要進(jìn)行任何操作，因為 num1 中剩余的元素本來就在 num1 中
   
   時間復(fù)雜度：O(m+n)
   空間復(fù)雜度：O(1)

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    // end1、end2：分別標(biāo)記nums1 和 nums2最后一個有效元素位置
    // end標(biāo)記nums1的末尾，因為nums1和nums2中的元素從后往前往nums1中存放
    // ，否則會存在數(shù)據(jù)覆蓋
    int end1 = m-1;
    int end2 = n-1;
    int index = m+n-1;

    // 從后往前遍歷，將num1或者nums2中較大的元素往num1中end位置搬移
    // 直到將num1或者num2中有效元素全部搬移完
    while(end1 >= 0 && end2 >= 0)
    {
        if(nums1[end1] > nums2[end2])
        {
            nums1[index--] = nums1[end1--];
        }
        else
        {
            nums1[index--] = nums2[end2--];
        }
    }

    // num2中的元素可能沒有搬移完，將剩余的元素繼續(xù)往nums1中搬移
    while(end2 >= 0)
    {
        nums1[index--] = nums2[end2--];
    }
    // num1中剩余元素沒有搬移完 ---不用管了，因為num1中剩余的元素本來就在num1中
}

如果大家有什么疑問可以在評論區(qū)與我討論，或者直接私信我，感謝大家的閱讀哦 ~文章來源地址http://www.zghlxwxcb.cn/news/detail-757081.html

到了這里，關(guān)于力扣每日一道系列 --- LeetCode 88. 合并兩個有序數(shù)組的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！