思路1：暴力求解
- 首先创建一个临时数组，其大小为第一个数组的大小（即nums1Size），其作用主要是。
- 通过循环遍历两个数组，将两个数组元素比较后较小的元素依次加入到临时数组中，直到有一个数组遍历完即可（注意：这里遍历完是只有效元素被遍历完，因为nums1中有无效元素0）。
- 将未遍历完的数组剩下的元素依次加入到临时数组中。
- 将临时数组中的元素依次拷贝到nums1数组中。
- 释放临时数组的空间。
时间复杂度：O(m+n)
空间复杂度：O(m+n)
值得注意的是： 这里需要考略到两种特殊情况需要单独处理
nums2数组为空时，nums1数组就是两个数组排序后的结果，函数不需要执行任何操作，直接return即可nums1数组中有效的元素个数为0（即m = 0） 时，此时nums2数组中的元素就是两个数组排序后的结果，此时只需要将nums2中的数组元素拷贝到nums1数组即可。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ if(nums2==NULL) { return; } else if(m==0) { for(int i=0;i<nums1Size;i++) { nums1[i]=nums2[i]; } } //创建一个数组来临时存放排序之后的元素，元素个数为m+n = nums1Size int *arr = (int*)malloc((nums1Size)*sizeof(int)); int index = 0,dest = 0,src = 0; //dest和src分别标记访问当前数组元素的下标 //index标记临时数组加入元素的下标位置 //依次遍历两个数组，直到有一个数组遍历完为止 while(dest < m && src < n) { if(nums1[dest]<=nums2[src]) { arr[index++] = nums1[dest++]; } else { arr[index++] = nums2[src++]; } } //将未遍历完的数组剩下的元素加入到临时数组中 if(src>=n) { while(dest<m) { arr[index++] = nums1[dest++]; } } else if(dest>=m) { while(src<n) { arr[index++] = nums2[src++]; } } //将临时数组中的元素依次赋值给nums1数组中对应位置的元素 for(int i = 0;i<nums1Size;i++) { nums1[i] = arr[i]; } free(arr);//将创建的数组空间释放 }
思路2：原地合并
- 从后往前遍历数组，将
nums1和nums2中的元素逐个比较，将较大的元素往nums1末尾进行搬移- 第一步结束后，
nums2中可能会有数据没有搬移完，将nums2中剩余的元素逐个搬移到nums1- 如果
num1中剩余元素没有搬移完，就不需要进行任何操作，因为num1中剩余的元素本来就在num1中
时间复杂度：O(m+n)
空间复杂度：O(1)
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ // end1、end2：分别标记nums1 和 nums2最后一个有效元素位置 // end标记nums1的末尾，因为nums1和nums2中的元素从后往前往nums1中存放 // ，否则会存在数据覆盖 int end1 = m-1; int end2 = n-1; int index = m+n-1; // 从后往前遍历，将num1或者nums2中较大的元素往num1中end位置搬移 // 直到将num1或者num2中有效元素全部搬移完 while(end1 >= 0 && end2 >= 0) { if(nums1[end1] > nums2[end2]) { nums1[index--] = nums1[end1--]; } else { nums1[index--] = nums2[end2--]; } } // num2中的元素可能没有搬移完，将剩余的元素继续往nums1中搬移 while(end2 >= 0) { nums1[index--] = nums2[end2--]; } // num1中剩余元素没有搬移完 ---不用管了，因为num1中剩余的元素本来就在num1中 }
如果大家有什么疑问可以在评论区与我讨论，或者直接私信我，感谢大家的阅读哦 ~
