题目描述：

给你两个按 非递减顺序 排列的整数数组 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、注意题目：nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0，nums2 的长度为 n

2、题目中明确nums1中后n个元素为0，且nums2的长度为n；那么直接用nums2中的有效元素替换掉nums1中value=0的下标位，再对nums1进行排序，over，直接开整

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int i = 0;int j = 0;// 用nums2中的元素值直接替换nums1中的0while (i < nums1Size && j < nums2Size) {if (nums1[i] == 0) {nums1[i] = nums2[j];j++;}i++;}// 不知道什么排序，冒泡？ 反正是排上了for (int i = 0; i < nums1Size - 1; i++) {for (int j = i + 1; j < nums1Size; j++) {if (nums1[i] > nums1[j]) {int temp = nums1[j];nums1[j] = nums1[i];nums1[i] = temp;   }}}
}

3、运行提交没有问题，测试用例ok，抄作业是足够了；但进阶要求时间复杂度为O(m+n)，解题思路也有点挫，学习一下其他优解~

---

优解思路&解法一（C）-- 直接合并后排序：

将数组nums2放进数组nums1的尾部，然后直接对整个数组进行排序.....

int cmp(int* a, int* b) {return *a - *b;
}void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {for (int i = 0; i < n; i++) {nums1[m + i] = nums2[i];}qsort(nums1, nums1Size, sizeof(int), cmp);
}

时间复杂度：排序序列长度为 m+n，套用快速排序的时间复杂度即可，平均情况为 O((m+n)log(m+n));

空间复杂度：排序序列长度为 m+n，套用快速排序的空间复杂度即可，平均情况为 O(log(m+n));

知识点：快速排序的空间复杂度为 排序序列长度，时间复杂度为 序列长度*log(序列长度)

qsort方法介绍：

1、qsort是一种排序函数，可以对多种数组数据类型进行排序(结构体、字符串、整型等)

2、其使用的排序方法为快速排序，且使用时需要包含<stdlib.h>的头文件

3、函数声明：void qsort （void* base, size_t num, size_t size, int (*compar)(const void* p1, const void* p2)）;

void* base: 需要排序的数组地址

size_t num: 需要排序的数组元素个数

size_t size: 需要排序的单个数组元素大小

int (*compar)(const void* p1, const void* p2):  排序判断函数，自定义此函数来决定升序还是降序(*p1 - *p2 升序，*p2 - *p1降序)

java实现：

java">public static void merge(int[] nums1, int m, int[] nums2, int n) {for (int i = 0; i < n; i++) {nums1[m+i] = nums2[i];}Arrays.sort(nums1);
}

和C实现基本类似，Arrays.sort()方法更简洁一些；

Arrays.sort()方法介绍：

1、Arrays.sort()是JAVA提供的静态方法，用于对数组进行排序(默认升序)，位于java.util.Arrays类中，使用前需import

2、对基础数据类型，使用双轴快速排序；对对象类型，使用TimSort（归并排序的改进版）

3、范围排序时需确保索引合法；对象排序需保证实现Comparable或提供自定义比较器

---

优解思路&解法二（C） -- 双指针

方法一虽然ok，但没有利用nums1和nums2已经被排序的性质，我们可以将nums1和nums2看作两个队列，每次将两个队列头部比较小的数字放到nums3中（需额外开辟）

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int p1 = 0;int p2 = 0;int* nums3 = (int *)malloc((m+n)*sizeof(int));int temp;while (p1 < m || p2 < n) {if (p1 == m) {temp = nums2[p2++];}else if (p2 == n) {temp = nums1[p1++];}else if (nums1[p1] < nums2[p2]) {temp = nums1[p1++];}else {temp = nums2[p2++];}nums3[p2 + p1 - 1] = temp;}for (int i = 0; i < m + n; i++) {nums1[i] = nums3[i];}free(nums3);
}

时间复杂度：O(m+n)  指针移动单调递增，最多移动m+n次，因此时间复杂度为O(m+n)

空间复杂度：O(m+n)  需要建立长度为m+n的中间数组nums3

注意点：if else的顺序要注意，如果else if (nums1[p1] < nums2[p2])逻辑在最前时，会出现当nums1[p1]==0时，条件会一直满足，p1一直++导致越界

java实现：

java">public static void merge(int[] nums1, int m, int[] nums2, int n) {int p1 = 0;int p2 = 0;int temp = 0;int[] nums3 = new int[m+n];while (p1 < m || p2 < n) {if (p1 == m) {temp = nums2[p2++];} else if (p2 == n) {temp = nums1[p1++];} else if (nums1[p1] < nums2[p2]) {temp = nums1[p1++];} else {temp = nums2[p2++];}nums3[p1+p2-1] = temp;}for (int i = 0; i < m+n; i++) {nums1[i] = nums3[i];}}

---

优解思路&解法三（C）-- 逆向双指针

方法二也是ok的，但额外开辟了m+n的空间；已知nums1的空间足够容纳nums2中的元素，且nums1和nums2都是有序数组，nums1中最大的数为nums1[m-1]，nums2中最大的数为nums2[n-1]，我们可以逆向比较两个数组的最大值，放入nums1[m+n-1]的位置中，以此递减；

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int p1 = m - 1;int p2 = n - 1;int p3 = m + n - 1;int temp = 0;while (p1 > -1 || p2 > -1) {if (p1 == -1) {temp = nums2[p2--];}else if (p2 == -1) {temp = nums1[p1--];}else if (nums1[p1] < nums2[p2]) {temp = nums2[p2--];}else {temp = nums1[p1--];}nums1[p3--] = temp;}
}

时间复杂度：O(m+n) 指针移动单调递减，最多移动m+n次，因此时间复杂度为O(m+n)

空间复杂度：直接对数组nums1原地修改，不需要额外空间

java实现：

java">public static void merge(int[] nums1, int m, int[] nums2, int n) {int p1 = m - 1;int p2 = n - 1;int temp = 0;int p3 = m + n - 1;while (p1 > -1 || p2 > -1) {if (p1 == -1) {temp = nums2[p2--];} else if (p2 == -1) {temp = nums1[p1--];} else if (nums1[p1] < nums2[p2]) {temp = nums2[p2--];} else {temp = nums1[p1--];}nums1[p3--] = temp;}		
}