百度蜘蛛网站wordpress定时发布文章

链接奉上：合并两个有序数组

直接合并后排序：

思路：

将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];}
}

这段代码业务逻辑就更加清晰，我们也要学习这样的代码风格，

欢迎讨论。