文章目录
- 思路1：暴力求解
- 思路2：原地合并
LeetCode 88. 合并两个有序数组
思路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 = nums1Sizeint *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中
}
如果大家有什么疑问可以在评论区与我讨论，或者直接私信我，感谢大家的阅读哦 ~
