20200623-88.merge-sorted-array.md

#88.merge-sorted-array

题目链接：https://leetcode-cn.com/problems/merge-sorted-array/

参考链接：https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetcode/

题目

给你两个有序整数数组 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]

解题

思路[1]jsAPI

• 将数组合并然后排序

代码

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
  nums1.splice(m);
  nums1.push(...nums2.slice(0, n));
  nums1.sort((a, b) => a - b)
};

思路[2]双指针从头遍历

• 将nums1复制出来，然后双指针指向两个数组头部，第三个指针指向nums1的头部，比较大小，小的放进nums1，移动指针，直到某个数组处理完成
• 将另一个没放完的数组剩余部分填充到数组后面

代码

var merge = function(nums1, m, nums2, n) {
  var p = 0, q = 0, r = 0;
  var copy = [...nums1];
  while((p < m) && (q < n)){
    if(copy[p] < nums2[q]){
      nums1[r] = copy[p];
      r++;
      p++;
      continue;
    }
    nums1[r] = nums2[q];
    r++;
    q++;
  }
  if(p < m){
    nums1.splice(p+q, m+n-p-q+1, ...copy.slice(p, m))
  }
  if(q < n){
    nums1.splice(p+q, m+n-p-q+1, ...nums2.slice(q, n))
  }
};

思路[3]三指针从尾部遍历

• 从尾部遍历，双指针指向两个数组尾部，第三个指针指向m+n-1的位置，比较大小，大的放入第三个指针的位置，往前移动指针
• 直到某一个小于0代表处理完成
• 如果nums2数组未处理完成，则将剩余元素放到nums1数组前q位

代码

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
  var p = m - 1, q = n - 1, r = m + n - 1;
  while((p >= 0) && (q >= 0)){
    if(nums1[p] > nums2[q]){
      nums1[r] = nums1[p];
      r--;
      p--;
      continue;
    }
    nums1[r] = nums2[q];
    r--;
    q--;
  }
  if(q >= 0){
    nums1.splice(0, q+1, ...nums2.slice(0, q+1))
  }
};

思考

• 数组问题还是指针比较好用