数组在我们平常工作中，是经常会使用的一个数据结构，本篇文章就准备借助一道算法题来让我们能更加熟练地使用它，废话不多说，开搞！

ppx.jpg

正文

给你如下题目，请思考下如何进行合并

qidai.jpeg

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n

看到这个题目，我们可以归纳出如下两个关键点

  1. nums1和nums2都是 递增排列的
  2. 合并后的结果应该存在 nums1 中，且也是递增排列的

下面我会给出两种方法来求解

bengdi.jpeg

方法一

方法一是我们最容易想到的，也就是忽略两个数组已经是有序的前提，直接将两个数组进行合并，然后将合并后的结果再进行排序，最终达到目的，代码如下

1
2
3
4
5
function merge(nums1, m, nums2, n) {
   nums1.length = m
   nums1.push(...nums2)
   nums1.sort((a,b)=>a-b)
}

这种方式会将 所有元素 进行一次重新排序，没有利用nums1和nums2 已经有序 的前提，因此该方式不是最优解

方法二

方法二主要利用 双指针的方式 以及nums1和nums2 已经有序的前提，以 O(m+n) 的时间复杂度实现合并，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function merge(nums1, m, nums2, n) {
   const tmp = []
   const total = m+n
   for(let i = 0,nums1Index=0,nums2Index=0;i<total;i++) {
        if(nums1Index >= m) {
            tmp[i] = nums2[nums2Index++]
        }else if(nums2Index >= n){
            tmp[i] = nums1[nums1Index++]
        }else if(nums1[nums1Index] <= nums2[nums2Index]) {
            tmp[i] = nums1[nums1Index++]
        }else {
            tmp[i] = nums2[nums2Index++]
        }
   }
   
   for(let i = 0;i<tmp.length;i++) {
        nums1[i] = tmp[i]
   }
}

分析下以上的代码

  1. 设置nums1和nums2的两个指针，分别进行遍历
  2. 总的遍历次数设为 m+n
  3. 设置一个 临时数组，用于存放排序后的结果
  4. 当nums1或nums2被遍历完成时，就直接取另一个的值，放到临时数组里
  5. 当nums1或nums2都未被遍历完成时，进行比较，并将 更小的值 放入临时数组中
  6. 最后对临时数组进行一次遍历，将排序后的值依次放入nums1中