题目:
方法1:直接合并后排序
思路:由于题目中已经告诉了这是一个有序数组,所以要将数组合并,我们可以先把nums2数组中的元素尾插到nums1中,再利用排序的方法实现有序。
这里我们利用比较简单的冒泡排序:我们一趟一趟的去比较大小,调整数据的位置。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int i=0;for(i=0;i<n;i++){nums1[m]=nums2[i];m++;}for(i=0;i<m+n-1;i++){int j=0;for(j=0;j<m+n-1;i++){if(nums1[j]>=nums1[j+1]){int tmp=nums1[j];nums1[j]=nums1[j+1];nums1[j]=tmp;}}}
}
当我们去运行代码的时候,系统报错说超出时间限制,这和前面的轮转数组类似,是因为时间复杂度太大(O(n^2)),所以存在更好的解决办法。
方法2:双指针法
思路:我们不是要按顺序去排列数组嘛,那我就让两个数组中的元素进行比较,如果我比较大,那么我的数据就放到指定位置,我再往后移动一位,再进行比较,就这样我们总能得到一个升序数组。但是有一个问题来了,我从哪个位置开始比较呢?
1)有同学说我想从头位置进行比较,既然提出了那我们就来分析分析这种办法可不可行!
既然要从头位置开始查并且是升序的数组,那我们就得把小数据往指定位置放,因此如果从头位置开始,我们就要将两数之中较小的放入。
当我们去分析时,你会发现按照将较小数据往index位置放时,会有数据被覆盖的情况。所以这种不方法不是很好,所以我们换个位置,我们从尾部开始比较。
2)从尾部进行比较。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int src=m-1;int dst=n-1;int index=m+n-1;while(src>=0&&dst>=0){if(nums1[src]>nums2[dst]){nums1[index]=nums1[src];src--;index--;}else{nums1[index]=nums2[dst];dst--;index--;}}while(dst>=0){nums1[index]=nums2[dst];dst--;index--;}
}