合并两个有序数组

    数组 双指针

    题目描述

    给定两个按升序排列的整数数组 nums1 和 nums2，以及两个整数 m 和 n，分别表示 nums1 和 nums2 中有效元素的个数。nums1 的总长度为 m + n，其中后 n 个位置被预留为空缓冲区。要求将 nums2 中的所有元素合并到 nums1 中，使 nums1 成为一个完整的有序数组，且整个操作须就地完成，不得使用额外数组。

    解题思路

    最直接的想法是从头开始比较两个数组，逐一将较小的元素填入结果——但这样做每次都需要把 nums1 中尚未处理的元素整体后移，效率较低。更优雅的做法是从尾部向前合并。

    由于 nums1 末尾已经预留了足够的空位，我们可以安全地从后往前写入，而不会覆盖任何还未处理的有效元素。具体来说，维护三个指针：p1 初始指向 nums1 最后一个有效元素（索引 m - 1），p2 指向 nums2 的末尾（索引 n - 1），p 指向 nums1 的最后一个位置（索引 m + n - 1）作为当前写入位置。

    每次迭代，比较 nums1[p1] 与 nums2[p2]，将较大的那个写到 nums1[p]，然后将对应的源指针和写入指针各自向前移动一步。如果 nums1 的有效部分已经全部处理完（p1 < 0），则直接将 nums2 剩余元素依次写入。当 p2 < 0 时，说明 nums2 已全部就位，循环结束——此时 nums1 中仍未被覆盖的前缀本就是有序的，无需额外处理。

    示例代码

    /**
 * 将两个已排序的数组合并到第一个数组中（就地替换）。
 *
 * @param {number[]} nums1 - 目标数组，长度至少为 m + n。前 m 个元素已按升序排列，其余位置可用作合并后数组的缓冲区。
 * @param {number[]} nums2 - 要合并进 nums1 的数组，长度为 n，已按升序排列。
 * @param {number} m - nums1 中有效元素的个数（从索引 0 到 m-1）。
 * @param {number} n - nums2 的长度（有效元素个数）。
 * @returns {number[]} 经过合并后的 nums1（直接修改传入的 nums1 并返回它）。
 */
export function mergeTwoArr(nums1, nums2, m, n) {
  // 初始化三个指针：p1 指向 nums1 的最后一个有效元素，p2 指向 nums2 的最后一个元素，
  // p 指向 nums1 的最后一个位置（目标写入位置）。
  let p1 = m - 1;
  let p2 = n - 1;
  let p = m + n - 1;

  // 只要 nums2 还有元素，就继续合并。若 nums1 先耗尽，剩下的 nums2 元素会直接写入 nums1。
  while (p2 >= 0) {
    // 如果 nums1 还有可比较元素，且 nums1 当前元素大于 nums2 当前元素，则写入 nums1 的元素；
    // 否则写入 nums2 的元素。
    if (p1 >= 0 && nums1[p1] > nums2[p2]) {
      nums1[p] = nums1[p1];
      p1--;
    } else {
      nums1[p] = nums2[p2];
      p2--;
    }
    // 移动写入指针到下一个位置
    p--;
  }

  return nums1;
}

// 测试
console.log('mergeTwoArr:', mergeTwoArr([1, 2, 3, 0, 0, 0], [2, 5, 6], 3, 3));
console.log('mergeTwoArr:', mergeTwoArr([0], [1], 0, 1));

    复杂度分析

    时间复杂度 为 O(m + n)。每个元素恰好被访问并写入一次，三个指针共同遍历了两个数组的全部 m + n 个元素，没有任何重复比较或元素移位操作。

    空间复杂度 为 O(1)。算法在 nums1 原有的缓冲区内完成所有写操作，除三个整型指针变量外不占用任何额外空间，是真正意义上的原地合并。