【算法详解】力扣88.合并两个有序数组

一、题目介绍

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 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] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

二、C++题解

方法一：

// 将数组2直接放到数组1的末端，然后整体对数组1排序。
// 但是此方法没有利用到非递减数组的特性，不是最优解
for (int i = 0; i < n; ++i) {
     nums1[m + i] = nums2[i];
}
sort(nums1.begin(), nums1.end());

方法二：从末尾往前依次填入，类似拉拉链

int i = m - 1, j = n - 1;
int p = nums1.size() - 1;

while (i >= 0 && j >= 0) {
    if (nums1[i] > nums2[j]) {
        nums1[p] = nums1[i];
        --i;
    } else {
        nums1[p] = nums2[j];
        --j;
    }
    --p;
}

// 如果nums2还有剩余
while (j >= 0) {
    nums1[p] = nums2[j];
    --j;
    --p;
}

三、思路分析

对于单链表来说，我们直接用双指针从头开始合并即可，但对于数组来说会出问题。因为题目让我直接把结果存到 nums1 中，而 nums1 的开头有元素，如果我们无脑复制单链表的逻辑，会覆盖掉 nums1 的原始元素，导致错误。

但 nums1 后面是空的呀，所以这道题需要我们稍微变通一下：将双指针初始化在数组的尾部，然后从后向前进行合并，这样即便覆盖了 nums1 中的元素，这些元素也必然早就被用过了，不会影响答案的正确性。