题目信息

题目地址：https://leetcode-cn.com/problems/merge-sorted-array/

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

说明：

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

示例：

1
2
3
4
5
输入：
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

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

提示：

1
2
3
-10^9 <= nums1[i], nums2[i] <= 10^9
nums1.length == m + n
nums2.length == n

解法一：双指针（顺序扫描）

很直接的就是双指针扫描，与上次我们在链表时写过【合并有序链表】同样的通过扫描与大小比较最终扫描完两个序列（m+n），前者是新建一个头节点然后遍历过程中慢慢连。这边也是可以创建一个数组，每扫描一个往里面设置值。

看下题目可知实际的元素数量是m,n完整数组是可能有多余空间，并且num1的空闲可以容纳nums2的有效元素，就是说我们直接把nums1作为结果数组，新建的数组装num1的实际元素

有了思路之后理一下具体的过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public void merge(int[] nums1, int m, int[] nums2, int n) {
    // 1.得到num1实际元素的数组
    int [] nums1_copy = new int[m];
    /*
    for(int i = 0; i < m; i++){
        nums1_copy[i] = nums[i];
    }
    */
    System.arraycopy(nums1, 0, nums1_copy, 0, m);
    
    // 扫描两个素材数组的指针
    int p = 0;
    int q = 0;
    // 结果数组（num1）待设值位置的指针
    int cur = 0;

    // 2.挨个比较设值
    while ((p < m) && (q < n)){
        nums1[cur++] = (nums1_copy[p] < nums2[q]) ? nums1_copy[p++] : nums2[q++];
    }

    // 3.加入最后多余的一段
    if (p < m)
      System.arraycopy(nums1_copy, p, nums1, p + q, m + n - p - q);
    if (q < n)
      System.arraycopy(nums2, q, nums1, p + q, m + n - p - q);
}

时间有三组操作m+min(m,n)+(m-n)或(n-m)因此为m+n,遍历了两组元素嘛O（m+n）
空间就是nums1_copy也就是O（m）

解法二：双指针（逆序）

解这题一开始我就在想是不是原地就可以（不用创建数组），但如果在解法一的过程中把num2的值设过去，那边就必须得存被替换的值。并且可能一直是num2小也是说那边还是需要一个中间数组。

也就是为了那一块的值创建了m大小的数组，为什么我们能拿num1为结果数组？
不就是它有空闲的一块地方么，那么我们何必不用呢！反而另开一块呢！直接用后面的地方不就不存在替换了吗！

因此我们就用后面这块，直接倒序设值，整理过程如下：

情况一：最终前面小的一块在num1

情况一：最终前面小的一块在num2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void merge(int[] nums1, int m, int[] nums2, int n) {
    // 定义两个指针并指向元素末端
    int p = m - 1;
    int q = n - 1;
    // 注意初始化当前指针在整个元素m+n的末端并不是整个num1的末端
    int cur = m + n - 1;

    // 1.挨个比较设值
    while (p >= 0 && q >= 0){
        nums1[cur--] = (nums1[p] < nums2[q]) ? nums2[q--] : nums1[p--];
    } 
    // 2.可能nums2前面有余
    System.arraycopy(nums2, 0, nums1, 0, q + 1);
}

时间复杂度仍然是不可避免的O(m+n)
空间复杂度O(1)

总结

这题还是比较简单的，主要是考虑到添加缓存与当前空间的问题。很多时候我们的中间变量或者中间数组是否真的该加。场上是否有不用的空间不用的变量，这是我们需要考虑的！剔除冗余无效代码