链接奉上:合并两个有序数组
目录
- 直接合并后排序:
- 思路:
- 代码实现:
- 双指针
- 思路:
- 代码实现:
直接合并后排序:
思路:
将nums2直接合并到nums1后边,并进行排序
代码实现:
#include<stdlib.h>int 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)//若n<1,进行判断时会发生越界现象;else{while(1){ //当count1+count2相加等于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];}
}
这段代码业务逻辑就更加清晰,我们也要学习这样的代码风格,
欢迎讨论。