LeetCode - 0088 合并两个有序数组

题目地址：https://leetcode.cn/problems/merge-sorted-array/description/

引言：话接上回，由于上次面试官着急下班，面试不得不提前终止，这不，他又找我去面试了

面试官：你好，小伙子，我们又见面了，上次看你的基础还不错，所以这次再好好面下你，请看下面的题目

合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素个数。
请你 合并 nums2到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
**注意：**最终合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

for example

输入：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] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

我看了下题目，思考片刻，暂时没有啥头绪，先来个笨办法。

我：这道题目可以这样，先定义一个新的数组，长度为 $m+n$，通过两个指针，逐个比较两个数组的每一个数，按照从小到大的顺序填入新数组，最后将新数组的数复制到 nums1 ，下面是我的代码

public void merge(int[] nums1, int m, int[] nums2, int n) {
    // 定义两个指针p1,p2，分别指向第一个数组和第二个数组的第一个元素
    int p1 = 0, p2 = 0; 
    int[] sorted = new int[m + n]; // 存储合并后的数组
    int cur; // 当前遍历到的元素

    // 遍历两个数组，当满足p1 < m || p2 < n时，肯定有数组没有遍历完
    while (p1 < m || p2 < n) {
        if (p1 == m) { // 第一个数组已经遍历完，直接取第二个数组的元素
            cur = nums2[p2++];
        } else if (p2 == n) { // 第二个数组已经遍历完，直接取第一个数组的元素
            cur = nums1[p1++];
        } else if (nums1[p1] < nums2[p2]) { // 如果第一个数组的当前元素比第二个数组当前元素小，则将第一个数组当前元素加入到 sorted 中
            cur = nums1[p1++];
        } else { // 否则，将第二个数组当前元素加入到 sorted 中
            cur = nums2[p2++];
        }
        // 将当前遍历到的元素加入到 sorted 数组中
        sorted[p1 + p2 - 1] = cur; 
    }

    // 将 sorted 数组中的元素复制到 nums1 数组中
    for (int i = 0; i < m + n; i++) {
        nums1[i] = sorted[i];
    }
}

面试官：嗯，看起来还可以，你可以解释下sorted[p1 + p2 - 1] = cur这句代码吗，我不是很懂。

我：其实很简单，当我们将一个元素加入到sorted数组时，我们使用表达式p1 + p2 - 1来确定该元素在sorted数组中的索引位置。这是因为我们在每次迭代中只会更新p1或p2的值，因此p1 + p2的结果减去1就是当前元素在sorted数组中的索引。

面试官：O ,懂了，你这个算法的时间复杂度是 $O(m+n)$ ,空间复杂度也是 $O(m+n)$ ,你可以不去引入新的数组来解决这个问题么？可不可以就在nums1数组上进行操作呢？

我：可以的，我们直接在nums1上进行操作。
首先，定义三个指针 p1、p2 和 p3，其中 p1 指向 nums1 中的最后一个元素 $m-1$，p2 指向 nums2 中的最后一个元素 $n-1$ ，p3 指向合并后数组的最后一个位置 $m+n-1$。如下图所示

我：使用 while 循环，只要 p1 和 p2 都没有遍历完，就进行比较

• 若 nums1[p1] 大于 nums2[p2]，将 nums1[p1] 放入nums1[p3]的位置，并将 p1 和 p3 向前移动一位。

• 若 nums1[p1] 不大于 nums2[p2]，将 nums2[p2] 放入nums1[p3]的位置，并将 p2 和 p3 向前移动一位。

• 如果 nums2 中还有元素未加入到nums1数组中，再将它们放入nums1数组中。

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1; // 指向 nums1 中最后一个元素的索引
    int p2 = n - 1; // 指向 nums2 中最后一个元素的索引
    int p3 = m + n - 1; // 指向合并后数组的最后一个位置的索引

    // 循环比较两个数组中的元素，将较大的元素放到nums1[p3]
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) { // 如果 nums1 当前元素大于 nums2 当前元素
            nums1[p3--] = nums1[p1--]; // 将 nums1 当前元素放入nums1数组的末尾，p1,p3向前移动
        } else { // 否则，将 nums2 当前元素放入nums1数组的末尾，p2,p3向前移动
            nums1[p3--] = nums2[p2--];
        }
    }

    // 如果 nums2 中还有元素未加入到nums1数组中，再将剩余的元素放入nums1数组中
    while (p2 >= 0) {
        nums1[p3--] = nums2[p2--];
    }
}

我：上面的算法就没有引入额外的数组，只是有少许额外的变量存储指针，空间复杂度降到了 $O(1)$ 。

面试官：不错不错，对这个问题分析的很好，思路清晰，看来你的数组题目还掌握的不错，尤其是利用指针来解决问题。那就回去等等通知吧，下一轮面试的时候我们再约时间，下一轮的题目可比这一次难哟，回家好好准备下。

我：好的，面试官。下次见！