河北涿州网站建设,装修网站有哪些,网站关键词被百度屏蔽怎么办,wordpress指定分类不显示图片链接奉上#xff1a;合并两个有序数组 目录 直接合并后排序#xff1a;思路#xff1a;代码实现#xff1a; 双指针思路#xff1a;代码实现#xff1a; 直接合并后排序#xff1a;
思路#xff1a; 将nums2直接合并到nums1后边#xff0c;并进行排序 代码实现合并两个有序数组 目录 直接合并后排序思路代码实现 双指针思路代码实现 直接合并后排序
思路 将nums2直接合并到nums1后边并进行排序 代码实现
#includestdlib.hint cmp(void* e1,void* e2)
{return *((int*)e1)-*((int*)e2);
}void merge(int* nums1,int numsSize1, int m,int* nums2, int numsSize2,int n)
{int j 0;for(int i m; i numsSize1;i){nums1[i] nums2[j];}qsort(nums1,numsSize1,4,cmp);
}双指针
思路 我们发现nums1与nums2已经是排序了的。 为了利用这一性质我们可以使用双指针方法。 这一方法将两个数组看作队列每次从两个数组头部取出比较小的数字放到结果中。 代码实现
初版
void merge(int* nums1,int numsSize1, int m,int* nums2, int numsSize2,int n)
{int arr[numsSize1];int count1 0;int count2 0;int i 0;if(n 1)//若n1进行判断时会发生越界现象;else{while(1){ //当count1count2相加等于numssize1说明数组arr已经装满了//就可以跳出循环if(count1 count2 numsSize1){break;}//这两个goto语句是为了防止nums1超出m时后会判断失误//或者nums2超出n时越界if(count1 m)goto flag2;if(count2 n)goto flag1;if(nums1[count1] nums2[count2]){flag1:arr[i] nums1[count1];}else{flag2:arr[i] nums2[count2];}}for(int i 0; i numsSize1; i){nums1[i] arr[i];}}
}进阶版 我们发现初版的代码包含了goto语句逻辑判断也比较令人摸不到头脑 于是
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int p1 0, p2 0;int sorted[m n];int cur;while (p1 m || p2 n) {if (p1 m) {cur nums2[p2];}else if (p2 n) {cur nums1[p1];}else if (nums1[p1] nums2[p2]) {cur nums1[p1];}else {cur nums2[p2];}sorted[p1 p2 - 1] cur;}for (int i 0; i ! m n; i) {nums1[i] sorted[i];}
}这段代码业务逻辑就更加清晰我们也要学习这样的代码风格
欢迎讨论。
