5.合并两个有序数组

书诚小驿2024/10/21前端面经算法JavaScript

合并两个有序数组

题目

给定两个已经按升序排列的整数数组 nums1 和 nums2,以及一个整数 m,nums1 的大小是 m + n,其中前 m 个元素表示已经填入的数字,后面的 n 个元素为 0,表示可以填充的数字个数。nums2 包含 n 个有效元素。你需要将 nums2 中的所有元素按照升序合并到 nums1 中,使得合并后的 nums1 仍然是一个有序数组。

示例

输入:nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
输出:nums1 被修改为 [1, 2, 2, 3, 5, 6]

参考答案

DETAILS

<script>
    function merge(nums1, m, nums2, n) {
      // 初始化指针
      let p1 = m - 1; // nums1 中已排序部分的最后一个元素索引
      let p2 = n - 1; // nums2 中最后一个元素的索引
      let p = m + n - 1; // 合并后数组的最后一个元素的索引

      // 从后向前合并数组
      while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
          nums1[p] = nums1[p1];
          p1--;
        } else {
          nums1[p] = nums2[p2];
          p2--;
        }
        p--;
      }

      // 如果 nums2 中还有剩余元素,直接复制到 nums1 中
      while (p2 >= 0) {
        nums1[p] = nums2[p2];
        p2--;
        p--;
      }

      // 注意:这里不需要处理 nums1 中剩余的元素,因为题目已说明 nums1 后面是 0,且 nums1 大小足够
    }

    // 示例用法
    let nums1 = [1, 2, 3, 0, 0, 0];
    let m = 3;
    let nums2 = [2, 5, 6];
    let n = 3;

    merge(nums1, m, nums2, n);

    console.log(nums1); // 输出: [1, 2, 2, 3, 5, 6]
  </script>

最后更新时间' 2025/2/23 01:48:16