合并有序数组

问题

给定两个按升序排列的数组，将它们合并为一个有序数组。

解答

方法一：双指针

function mergeSortedArrays(arr1, arr2) {
  const result = [];
  let i = 0; // arr1 指针
  let j = 0; // arr2 指针

  // 比较两个数组的元素，较小的放入结果
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      result.push(arr1[i]);
      i++;
    } else {
      result.push(arr2[j]);
      j++;
    }
  }

  // 处理剩余元素
  while (i < arr1.length) {
    result.push(arr1[i]);
    i++;
  }
  while (j < arr2.length) {
    result.push(arr2[j]);
    j++;
  }

  return result;
}

// 测试
console.log(mergeSortedArrays([1, 3, 5], [2, 4, 6])); // [1, 2, 3, 4, 5, 6]
console.log(mergeSortedArrays([1, 2, 3], [4, 5]));    // [1, 2, 3, 4, 5]
console.log(mergeSortedArrays([], [1, 2]));          // [1, 2]

方法二：原地合并（LeetCode 88）

当第一个数组有足够空间时，从后往前合并，避免元素覆盖。

function merge(nums1, m, nums2, n) {
  let p1 = m - 1;     // nums1 有效元素的末尾
  let p2 = n - 1;     // nums2 末尾
  let p = m + n - 1;  // 合并后数组的末尾

  // 从后往前填充
  while (p2 >= 0) {
    if (p1 >= 0 && nums1[p1] > nums2[p2]) {
      nums1[p] = nums1[p1];
      p1--;
    } else {
      nums1[p] = nums2[p2];
      p2--;
    }
    p--;
  }

  return nums1;
}

// 测试：nums1 长度为 m + n，后面用 0 占位
const nums1 = [1, 2, 3, 0, 0, 0];
merge(nums1, 3, [2, 5, 6], 3);
console.log(nums1); // [1, 2, 2, 3, 5, 6]

方法三：简洁写法

function mergeSortedArrays(arr1, arr2) {
  const result = [];
  let i = 0, j = 0;

  while (i < arr1.length || j < arr2.length) {
    if (j >= arr2.length || (i < arr1.length && arr1[i] <= arr2[j])) {
      result.push(arr1[i++]);
    } else {
      result.push(arr2[j++]);
    }
  }

  return result;
}

关键点

• 双指针法时间复杂度 O(m+n)，空间复杂度 O(m+n)
• 原地合并从后往前，避免覆盖未处理的元素
• 循环结束后要处理剩余元素
• 注意边界条件：空数组、长度不等的数组