网站建设目的和功能定位,在深圳的中建公司,注册个体工商户用于网站建设,网站服务器和空间#x1f4f7; 江池俊#xff1a; 个人主页 #x1f525;个人专栏#xff1a; ✅数据结构探索 ✅LeetCode每日一道 #x1f305; 有航道的人#xff0c;再渺小也不会迷途。 文章目录 思路1#xff1a;暴力求解思路2#xff1a;原地合并 LeetCode 88. 合并两个有序数组… 江池俊 个人主页 个人专栏 ✅数据结构探索 ✅LeetCode每日一道 有航道的人再渺小也不会迷途。 文章目录 思路1暴力求解思路2原地合并 LeetCode 88. 合并两个有序数组 思路1暴力求解 首先创建一个临时数组其大小为第一个数组的大小即nums1Size其作用主要是。通过循环遍历两个数组将两个数组元素比较后较小的元素依次加入到临时数组中直到有一个数组遍历完即可注意这里遍历完是只有效元素被遍历完因为nums1中有无效元素0。将未遍历完的数组剩下的元素依次加入到临时数组中。将临时数组中的元素依次拷贝到nums1数组中。释放临时数组的空间。 时间复杂度O(mn) 空间复杂度O(mn) 值得注意的是 这里需要考略到两种特殊情况需要单独处理
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(nums2NULL){return;}else if(m0){for(int i0;inums1Size;i){nums1[i]nums2[i];}}//创建一个数组来临时存放排序之后的元素元素个数为mn 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(srcn){while(destm){arr[index] nums1[dest];}}else if(destm){while(srcn){arr[index] nums2[src];}}//将临时数组中的元素依次赋值给nums1数组中对应位置的元素for(int i 0;inums1Size;i){nums1[i] arr[i];}free(arr);//将创建的数组空间释放
}思路2原地合并 从后往前遍历数组将 nums1 和 nums2 中的元素逐个比较将较大的元素往 nums1 末尾进行搬移第一步结束后nums2 中可能会有数据没有搬移完将 nums2 中剩余的元素逐个搬移到 nums1如果 num1 中剩余元素没有搬移完就不需要进行任何操作因为 num1 中剩余的元素本来就在 num1 中 时间复杂度O(mn) 空间复杂度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 mn-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中
}如果大家有什么疑问可以在评论区与我讨论或者直接私信我感谢大家的阅读哦 ~
