88.MergeTwoSortedArray

问题

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

解决方案

思路：申请一个大小是两个数组的临时空间用了存放排序后的元素，先对两个数组中的元素进行判断，小的放进临时数组中，直到一个数组放完后，把另外一个数组中的元素全部拷贝进去，最后将临时数组中的元素拷贝到原数组中。
以下是代码：

void merge(int* nums1, int m, int* nums2, int n)
{
	int cur1 = 0;
	int cur2 = 0;
	int index = 0;
	int *tmp = (int*)malloc(sizeof(int)*(m+n));
	assert(tmp);
	memset(tmp,0, m + n);
	while (cur1 < m && cur2 < n)
	{		
		if (nums1[cur1] < nums2[cur2])
		{
			tmp[index] = nums1[cur1];
			index++;
			cur1++;
		}
		else if(nums1[cur1] > nums2[cur2])
		{
			tmp[index] = nums2[cur2];
			index++;
			cur2++;
		}
		else if (nums1[cur1] == nums2[cur2])
		{
			tmp[index] = nums1[cur1];
			index++;
			tmp[index] = nums2[cur2];
			index++;
			cur1++;
			cur2++;
		}
	}

    //nums2没有元素，但nums1还有元素时，拷贝到tmp中
	while (cur1 < m)
	{
		tmp[index++] = nums1[cur1++];
	}
	//nums1没有元素，但nums2还有元素时，拷贝到tmp中
	while (cur2 < n)
	{
		tmp[index++] = nums2[cur2++];
	}

    // 将tmp中的元素放回nums1中
	for (int i = 0; i < m+n; i++)
	{
		nums1[i] = tmp[i];
	}

    //释放掉申请的空间
	free(tmp);
}

看了上面的代码，发现又长又繁琐，我们对其简化后的代码如下：

void Merge(int *nums1,int m,int *nums2,int n)
{
	int count = m + n - 1;
	--m, --n;
	while (n>=0 && m>=0)
	{
		nums1[count--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
	}

	while (m >= 0)
	{
		nums1[count--] = nums1[m--];
	}
}