# 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]

# 解题思路

提取题目中的重要的名词，两个有序数组、排成有序数组、原地排列不适用额外空间。也就是说我们需要：

利用数组的有序性
不能额外使用其他空间

分析：对于多个数组的排序，我们可能采取直接合并数组，然后再进行排序。这肯定是最暴力最低效的方法。题目中既然告诉了我们两个数组都是有序的，那么我们肯定要利用数组的有序性。既然要得到有序的数组，那么我们肯定要对两个数组中的元素一一进行比较，最关键的是比较的规则是什么了？

从小往大进行比较，比如。 nums1中的最小值1和nums2中的最小值2进行比较，1 < 2，因此1排在前面2要插在1的后面。 nums2中的2要继续与num1中的第二个数2比较，他们两个相等，因此，可以确定nums2中的2就是插入nums1中的2后面。将2插入进去，需要将nums1中后面所有元素往后移动一位。从上面的分析中我们可以看出，如果我们从小往大进行比较，那么插入时需要移动后面的元素。每次插入都需要移动。既然我们的元素是有序的，那么我们可不可以从后往前排列，这样的话就不需要移动后面的元素了。
从大往小进行比较。 nums1中最大值3与nums2中最大值6比较，6大于3。因此，将nums1的最后一位(m + n -1，这里nums1空间始终足够)赋值为6，n--; 最终如果nums1中所有的数都比较完了。nums2中还有剩余，只需要把nums2的数添加到nums1即可。

# 代码

var merge = function(nums1, m, nums2, n) {
  while(m > 0 && n > 0){
      if(nums2[n-1] >= nums1[m-1]){
          nums1[m + n -1] = nums2[--n];
      }else{
          nums1[m + n -1] = nums1[--m];
      }
  }
  // 剩余n个数
  while(n > 0){
      nums1[n-1] = nums2[--n];
  }
};

我们只需要定义一个指针来记录数组中当前不重复的元素位置，我们查找到不重复元素就把它赋值为下一个位置即可。

← 【0026—删除排序数组中的重复项】