leetcode-88-Merge Sorted Array
leetcode-88-Merge Sorted Array
题目描述：
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
- The number of elements initialized in nums1 and nums2 are m and n respectively.
- You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]要完成的函数：
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
说明：
1、这道题给定两个vector，nums1和nums2，以及两个整数，m和n，nums1的前m个数是排序好的，nums2的前n个数是排序好的，要求把这m+n个数排好序，放在nums1这个vector中（nums1中有充足的空间来放m+n个数）。
2、明白题意，这道题目不难完成，我们设定两个index，i=m-1，j=n-1，从后面开始比较，如果nums2[j]>=nums1[i]，就把nums2[j]的数值放在nums1[i+j+1]中，接着j--。
如果nums2[j]<nums1[i]，那么把nums1[i]的数值放在nums1[i+j+1]中，i++。
不断循环，直到i==-1或者j==-1（表示已经处理完其中一个vector了），结束循环。
这部分代码如下：
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
int i=m-1,j=n-1;
while(j>=0&&i>=0)
{
if(nums1[i]>nums2[j])
{
nums1[i+j+1]=nums1[i];
i--;
}
else
{
nums1[i+j+1]=nums2[j];
j--;
}
}
}结束了循环之后，有可能是nums2处理完了，也就是j==-1这种情况，比如nums1=[1,2,5,0,0,0]，nums2=[2,3,4]，这时候nums1=[1,2,2,3,4,5]，我们不需要其他处理，nums1就是我们要的结果。
也有可能是nums1处理完了，nums2还没处理完，比如nums1=[8,9,10,0,0,0]，nums2=[1,2,12]，上述代码处理完结果是[8,9,8,9,10,12]，我们还没有把nums2中的1和2放到nums1中去。
所以完整代码如下：
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
int i=m-1,j=n-1;
while(j>=0&&i>=0)
{
if(nums1[i]>nums2[j])
{
nums1[i+j+1]=nums1[i];
i--;
}
else
{
nums1[i+j+1]=nums2[j];
j--;
}
}
if(i==-1)//nums1处理完了，nums2还没处理完
{
while(j>=0)
{
nums1[i+j+1]=nums2[i+j+1];
j--;
}
}
}上述代码实测6ms，beats 99.93% of cpp submissions。
腾讯云开发者
