数组合并

2024年04月09日

柏拉文

越努力，越幸运

一、合并两个有序数组

给你两个按非递减顺序排列的整数数组 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 中的元素。

示例 2

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

1.1 逆向双指针

思路: 使用双指针策略从后往前地合并两个有序数组，避免了覆盖未处理的数据。为什么从后往前?: 因为 nums1 的尾部有足够的空间存放合并后的所有数字。如果从前往后合并，可能会覆盖掉还未处理的数据；而从后往前合并，则不会发生这种情况，因为我们总是在覆盖空白区域或已经处理过的位置。可以指针设置为从后向前遍历，每次取两者之中的较大者放进 nums1 的最后面。

变量初始化:

p1 = m - 1: 指向 nums1 中最后一个有效数字的下标。
p2 = n - 1: 指向 nums2 中最后一个数字的下标。
tail = m + n - 1: 指向合并后数组（仍存放在 nums1 中）的最后位置。

合并过程: 算法从后往前进行操作，步骤如下

循环条件: 只要 p1 >= 0 或 p2 >= 0，说明至少还有一个数组中有元素未处理。
比较并选择元素:
- 情况 1：如果 p1 === -1，说明 nums1 中的元素已经全部处理，此时直接从 nums2 中取剩余的数字：cur = nums2[p2--]。
- 情况 2：如果 p2 === -1，说明 nums2 已经全部处理，此时直接取 nums1 中剩余的数字：cur = nums1[p1--]。
- 情况 3：当两个数组都有剩余数字时，比较 nums1[p1] 与 nums2[p2]: 如果 nums1[p1] 大，则将它赋值给 cur 并将 p1 向左移动一位（p1--）。否则，取 nums2[p2] 赋值给 cur，同时 p2 向左移动一位（p2--）。
更新数组: 将选中的元素 cur 放到 nums1 的尾部位置，即 nums1[tail]，然后将 tail 向左移动一位。

实现

function merge(nums1, m, nums2, n) {
  let p1 = m - 1;
  let p2 = n - 1;
  let tail = m + n - 1;

  while (p1 >= 0 || p2 >= 0) {
    if (p1 < 0) {
      nums1[tail--] = nums2[p2--];
    } else if (p2 < 0) {
      nums1[tail--] = nums1[p1--];
    } else if (nums1[p1] < nums2[p2]) {
      nums1[tail--] = nums2[p2--];
    } else {
      nums1[tail--] = nums1[p1--];
    }
  }

  return nums1;
}

时间复杂度: $O(m+n)$ , 指针移动单调递减，最多移动 m+n 次，因此时间复杂度为 $O(m+n)$ 。
空间复杂度: $O(1)$ , 直接对数组 nums 原地修改，不需要额外空间。

一、合并两个有序数组​

1.1 逆向双指针​

一、合并两个有序数组

1.1 逆向双指针