题目Leetcode地址：

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

请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：

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

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1]

解释：需要合并 [1] 和 [] 。 合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1 输出：[1]

解释：需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。

注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

解题过程1.理解题意

该题主要是将数组num2合并到num1中，合并之后的数据还是按照升序进行排序

2.数据结构及算法思维选择

方案解法：看完题目，最先想到的方法就是将两个数组合并到一个数组中，并使用Arrays.sort(int[] a)方法进行排序。

数据结果：数组

算法思维：遍历，排序

3.Code基本解法以及编码实现

暴力破解

步骤

将数组num2的数字赋值到num1中使用Arrays.sort()方法对num1进行排序

边界问题

数组索引越界数组溢出边界

代码实现

class Solution {    public void merge(int[] nums1, int m, int[] nums2, int n) {        // 将nums2值赋值到nums1中        for(int i =0;i<n;i++){            nums1[i+m] = nums2[i];        }        // 排序        Arrays.sort(nums1);    }}

复杂度

时间复杂度

遍历数组：O(n)

数组排序：Arrays.sort()其时间复杂度为O(n*log(n))。

即最终的复杂度为：O(n*log(n))

空间复杂度

O(1)。 直接对数组 nums1原地修改，不需要额外空间。

LeetCode运行结果

执行结果：通过

4.Consider 思考更优解

暴力破解中的时间复杂度为O(n*log(n))，其原因是Arrays.sort()对基本类型数组使用快速排序，对象数组使用归并排序。而且将两个数组合并成一个数组之后，把之前的两个数组的非递减顺序这个破坏了，没有利用起来。那我们是不是可以思考利用这个非递减顺序这点呢？

5.Code 最优解思路及编码实现

优化解法1：双指针

步骤

申请一个数组，长度为m+n每次从两个数组头部取出比较小的数字放到结果中最后将排序好的数组赋值给num1

代码实现

class Solution {    public void merge(int[] nums1, int m, int[] nums2, int n) {        // 定义临时数组temp，并将数组的长度设置为m+n        int[] temp = new int[m+n];        int tp1 =0;        int tp2 =0;        int i=0;        // 每次从两个数组头部取出比较小的数字放到结果中        while (tp1 < m && tp2 < n){            if(nums1[tp1] < nums2[tp2]){                temp[i] = nums1[tp1];                tp1++;                i++;            }else {                temp[i] = nums2[tp2];                tp2++;                i++;            }        }        // 剩余的数组数值放到temp数组中        while (tp1<m){            temp[i] = nums1[tp1];            i++;            tp1++;        }        while (tp2<n){            temp[i]=nums2[tp2];            i++;            tp2++;        }        // 将结果赋值给nums1        for(int x=0;x<nums1.length;x++) {            nums1[x] = temp[x];        }    }}

复杂度

时间复杂度

指针遍历：O(n)

空间复杂度

申请了额外的数组：O(n)

LeetCode运行结果

执行结果：通过

优化解法2：逆向双指针

步骤

设置标识分别指向数组的最后一个值（nums1为nums[m-1] ，nums2为nums2[n-1]）每次从两个数组尾部取出比较大的数字放到结果中

代码实现

class Solution {    public void merge(int[] nums1, int m, int[] nums2, int n) {        int tp1 =m-1;        int tp2 = n-1;        int tail = m+n-1;        while (tp1 >-1 && tp2 >-1){            if(nums1[tp1] < nums2[tp2]){                nums1[tail] = nums2[tp2--];            }else {                nums1[tail] = nums1[tp1--];            }            tail--;        }        while (tp1 > -1){            nums1[tail] = nums1[tp1--];            tail--;        }        while (tp2 > -1){            nums1[tail] = nums2[tp2--];            tail--;        }    }}

复杂度

时间复杂度

指针遍历：O(n)

空间复杂度

O(1)。 直接对数组 nums1原地修改，不需要额外空间。

LeetCode运行结果

执行结果：通过