问题描述:给定两个已排序的数组,将第二个数组归并成到第一个数组,假定第一个数组的大小足够将第二个数组加进来
这一题一开始没有注意到前提条件是两个已排序的数组,一开始是先将第二个数据添加到第一个数组的尾部,然后在进行普通的归并排序,但是在本地运行正常,LeetCode老是WA,后来注意到了前提条件,对代码进行了简化,思路是从前面进行归并,并且不开一个新的数组来进行归并,无果。必须要使用一个新的数组开作为容器,才可以进行从前往后的归并。最后,根据正难则反的思路,从后面进行归并,顺利找出解决方法。
下面是C#的解决方案
public static void Merge(int[] nums1, int m, int[] nums2, int n)
{
int i = m-, j = n-; for(int k = m + n - ; k >= ; k--)
{
if (i < ) nums1[k] = nums2[j--]; //如果i小于0 说明num1的原始数据已经归并完毕,直接对num2进行归并
else if (j < ) nums1[k] = nums1[i--];//如果j小于0 说明num2的原始数据已经归并完毕,直接对num1进行归并
else if(nums1[i] > nums2[j]) nums1[k] = nums1[i--];
else nums1[k] = nums2[j--]; } }