sl1673495 / leetcode-javascript

:beers: 喝杯小酒,一起做题。前端攻城狮从零入门算法的宝藏题库,根据知名算法老师的经验总结了 100+ 道 LeetCode 力扣的经典题型 JavaScript 题解和思路。已按题目类型分 label,一起加油。
2.08k stars 344 forks source link

合并两个有序数组-88 #29

Open sl1673495 opened 4 years ago

sl1673495 commented 4 years ago

88.合并两个有序数组

给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。

示例:

输入:

nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

https://leetcode-cn.com/problems/merge-sorted-array

思路

从后往前的双指针思路,先定义指针 i 和 j 分别指向数组中有值的位置的末尾,再定义指针 k 指向待填充的数组 1 的末尾。

然后不断的迭代 i 和 j 指针,如果 i 位置的值比 j 大,就移动 i 位置的值到 k 位置,反之亦然。

如果 i 指针循环完了,j 指针的数组里还有值未处理的话,直接从 k 位置开始向前填充 j 指针数组即可。因为此时数组 1 原本的值一定全部被填充到了数组 1 的后面位置,且这些值一定全部大于此时 j 指针数组里的值。

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
let merge = function (arr1, m, arr2, n) {
  // 两个指针指向数组非空位置的末尾
  let i = m - 1;
  let j = n - 1;
  // 第三个指针指向第一个数组的末尾 填充数据
  let k = arr1.length - 1;

  while (i >= 0 && j >= 0) {
    let num1 = arr1[i];
    let num2 = arr2[j];

    if (num1 > num2) {
      arr1[k] = num1;
      i--;
    } else {
      arr1[k] = num2;
      j--;
    }
    k--;
  }

  while (j >= 0) {
    arr1[k] = arr2[j];
    j--;
    k--;
  }
};