力扣每日一道系列 --- LeetCode 88. 合并两个有序数组

在这里插入图片描述

📷 江池俊：个人主页

🔥个人专栏： ✅数据结构探索 ✅LeetCode每日一道
🌅 有航道的人，再渺小也不会迷途。

文章目录

- 思路1：暴力求解
- 思路2：原地合并

LeetCode 88. 合并两个有序数组

在这里插入图片描述

思路1：暴力求解

首先创建一个临时数组，其大小为第一个数组的大小（即nums1Size），其作用主要是。
通过循环遍历两个数组，将两个数组元素比较后较小的元素依次加入到临时数组中，直到有一个数组遍历完即可（注意：这里遍历完是只有效元素被遍历完，因为nums1中有无效元素0）。
将未遍历完的数组剩下的元素依次加入到临时数组中。
将临时数组中的元素依次拷贝到nums1数组中。
释放临时数组的空间。

时间复杂度：O(m+n)
空间复杂度：O(m+n)

值得注意的是： 这里需要考略到两种特殊情况需要单独处理

nums2 数组为空时，nums1 数组就是两个数组排序后的结果，函数不需要执行任何操作，直接 return 即可
nums1 数组中有效的元素个数为 0（即 m = 0 ）时，此时 nums2 数组中的元素就是两个数组排序后的结果，此时只需要将 nums2 中的数组元素拷贝到 nums1 数组即可。

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];
        }
    }
    //创建一个数组来临时存放排序之后的元素，元素个数为m+n = nums1Size
    int *arr = (int*)malloc((nums1Size)*sizeof(int));
    int index = 0,dest = 0,src = 0;
    //dest和src分别标记访问当前数组元素的下标
    //index标记临时数组加入元素的下标位置
    //依次遍历两个数组，直到有一个数组遍历完为止
    while(dest < m && src < n)
    {
        if(nums1[dest]<=nums2[src])
        {
            arr[index++] = nums1[dest++];
        }
        else
        {
            arr[index++] = nums2[src++];
        }
    }
    //将未遍历完的数组剩下的元素加入到临时数组中
    if(src>=n)
    {
        while(dest<m)
        {
            arr[index++] = nums1[dest++];
        }
    }
    else if(dest>=m)
    {
        while(src<n)
        {
            arr[index++] = nums2[src++];
        }
    }
    //将临时数组中的元素依次赋值给nums1数组中对应位置的元素
    for(int i = 0;i<nums1Size;i++)
    {
        nums1[i] = arr[i];
    }
    free(arr);//将创建的数组空间释放
}

思路2：原地合并

从后往前遍历数组，将 nums1 和 nums2 中的元素逐个比较，将较大的元素往 nums1 末尾进行搬移
第一步结束后，nums2 中可能会有数据没有搬移完，将 nums2 中剩余的元素逐个搬移到 nums1
如果 num1 中剩余元素没有搬移完，就不需要进行任何操作，因为 num1 中剩余的元素本来就在 num1 中

时间复杂度：O(m+n)
空间复杂度：O(1)

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    // end1、end2：分别标记nums1 和 nums2最后一个有效元素位置
    // end标记nums1的末尾，因为nums1和nums2中的元素从后往前往nums1中存放
    // ，否则会存在数据覆盖
    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中的元素可能没有搬移完，将剩余的元素继续往nums1中搬移
    while(end2 >= 0)
    {
        nums1[index--] = nums2[end2--];
    }
    // num1中剩余元素没有搬移完 ---不用管了，因为num1中剩余的元素本来就在num1中
}