原文：88. 合并两个有序数组(leetcode 解题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址：https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-088/

题目：

难度：Easy

相关话题：数组、双指针

给定两个有序整数数组nums1 和 nums2 ，将 nums2 合并到nums1 中， 使得num1 成为一个有序数组。

说明:

  • 初始化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]

思路：

归并排序的merge，但是由于需要原地修改，先将nums1的值往后移动直到边界，以避免覆盖；

例如：[1,2,3,4,0,0]，移动后变为[1,2,1,2,3,4]，移动后前2位[1,2]，就可以覆盖不影响后续merge。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @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) {
  for(let i=m-1;i>=0;i--){
    nums1[i+n]=nums1[i]
  }
  let i=n,j=0,id=0
  while(i<m+n || j<n){
    if(i===m+n) nums1[id]=nums2[j++]
    else if(j===n) nums1[id]=nums1[i++]
    else if(nums1[i]<nums2[j]) nums1[id]=nums1[i++]
    else if(nums1[i]>=nums2[j]) nums1[id]=nums2[j++]
    id++
  }
};

扩展阅读：