合并两个有序数组

合并两个有序数组

小哆啦今天开始每日更新力扣150算法题目。

题目链接88. 合并两个有序数组 - 力扣（LeetCode）

小哆啦的最初的做法

在遥远的代码星球上，小哆啦接到了一个任务——要把两个数组 nums1 和 nums2 合并成一个有序的大数组。他灵机一动，决定先搞个大盘子（新数组 arr），让两个小盘子里的数依次比大小，谁小就先跳到大盘子里。

于是小哆啦开始了以下操作：

1. 他站在两个数组的开头，左手拿着 nums1 的第一个数字，右手拿着 nums2 的第一个数字。
2. 小哆啦心想：“嘿，谁小谁先跳到大盘子里！我再挪个位置继续比。”
3. 如果一个盘子里的数字跳完了，小哆啦直接把另一个盘子里的所有数字统统倒进大盘子。

最后，他把大盘子里的数字一个个搬回到 nums1 的空位置，任务完成！

小哆啦的最初代码实现

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    let numFirIndex: number = 0, numSecIndex: number = 0; // 两个指针指向两个盘子的起始位置
    let arr: number[] = []; // 小哆啦的大盘子，用来临时存放合并后的结果

    // 开始“比大小游戏”
    while (numFirIndex < m || numSecIndex < n) {
        if (numFirIndex === m) {
            // nums1 的数字搬完了，剩下的全是 nums2 的
            arr.push(nums2[numSecIndex]);
            numSecIndex++;
        } else if (numSecIndex === n) {
            // nums2 的数字搬完了，剩下的全是 nums1 的
            arr.push(nums1[numFirIndex]);
            numFirIndex++;
        } else if (nums1[numFirIndex] <= nums2[numSecIndex]) {
            // nums1 的当前数字更小，放到大盘子里
            arr.push(nums1[numFirIndex]);
            numFirIndex++;
        } else {
            // nums2 的当前数字更小，放到大盘子里
            arr.push(nums2[numSecIndex]);
            numSecIndex++;
        }
    }

    // 把大盘子里的内容重新搬回 nums1
    for (let index: number = 0; index < m + n; index++) {
        nums1[index] = arr[index];
    }
}

时间复杂度 & 空间复杂度：

• 时间复杂度： O(m+n)
  小哆啦每次比较或搬运一个数字，总共要处理 m+n个数字，所以时间复杂度是线性的。
• 空间复杂度： O(m+n)
  大盘子 arr 的大小取决于两个数组的总长度，所以需要额外的 O(m+n)的空间来存储中间结果。

小哆啦的原地合并大冒险

厨房的主厨对他说：“小哆啦，你这方法不够优雅啊！”。

小哆啦挠了挠头，觉得很不服气，但他还是决定重新思考。
好嘞！让我们把这个故事写得更详细些，配合小哆啦的天才灵感，打造一个史诗级的代码故事！

天才的灵感

小哆啦猛然发现，nums1 其实很贴心地在后面给自己留了一大段空地（多出来的 0），这些空地完全可以用来直接放合并的结果啊！

于是，他兴奋地喊道：“我直接在 nums1 里操作，从后面开始比大小，把大数字依次放到后面的位置，这样就不会覆盖掉未处理的数据啦！”

就这样，小哆啦的“原地合并法”诞生了：

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    let numFirIndex: number = m - 1; // 指向 nums1 的有效部分的最后一个元素
    let numSecIndex: number = n - 1; // 指向 nums2 的最后一个元素
    let mergeIndex: number = m + n - 1; // 指向 nums1 的总长度最后一个位置

    // 从后往前合并数字
    while (numSecIndex >= 0) {
        if (numFirIndex >= 0 && nums1[numFirIndex] > nums2[numSecIndex]) {
            // 如果 nums1 的当前数字更大，就放到最后的位置
            nums1[mergeIndex] = nums1[numFirIndex];
            numFirIndex--;
        } else {
            // 如果 nums2 的当前数字更大（或等于），就放到最后的位置
            nums1[mergeIndex] = nums2[numSecIndex];
            numSecIndex--;
        }
        mergeIndex--; // 每次放完一个数字，往前挪一个位置
    }
}

详细解析

1. 两个指针，一个目标：

   • 小哆啦决定用两个指针分别指向 nums1 和 nums2 的最后一个有效数字。
   • 再用一个指针指向 nums1 的末尾（也就是空地的最后一个位置），每次比较后把更大的数字放到这里。

2. 从后往前，避免覆盖：

   • 因为 nums1 后面有一段空地，所以他从后往前填充，不会覆盖掉 nums1 的有效部分。

3. 特殊情况处理：

   • 如果 nums1 的有效数字用完了，直接把 nums2 剩下的数字搬过来。
   • 如果 nums2 的数字用完了，不用管了，因为 nums1 剩下的数字本身就已经有序。

4. 循环结束的条件：

   • 小哆啦只需要管 nums2 是否处理完，因为 nums1 的有效部分已经在目标数组里。

时间复杂度 & 空间复杂度

• 时间复杂度： O(m+n))
  小哆啦依次处理每个数字，总共 m+n 个数字，时间复杂度是线性的。

• 空间复杂度： O(1)
  小哆啦直接在 nums1 上操作，没有用额外的大盘子，内存利用率非常高

  这次，小哆啦的操作堪称艺术！
  他不仅完成了任务，还节约了空间，成为了代码星球上的“环保小达人”。
  现在，厨房宽敞了，锅碗瓢盆也不乱放，效率杠杠的