解题思路
遇到这种题要首先想到暴力法，AC后再考虑别的方法。
解法1：暴力法
直接将nums2拼到nums1后面，然后sort，过啦！(太水了)
代码如下：
vector<int> merge(vector<int> &nums1, int m, vector<int> &nums2, int n)
{
for(int i = 0; i < n; i++)
{
nums1[m + i] = nums2[i];
}
sort(nums1.begin(),nums1.end());
return nums1;
}
解法2：快慢指针法
使用双指针解决问题的思路非常重要。
- 如果nums1遍历完的时候，nums2还没遍历完————将nums2的剩余元素放到插入元素后的sorted数组后面；
- 如果nums2遍历完的时候，nums1还没遍历完————将nums1的剩余元素放到插入元素后的sorted数组后面；
- 如果二者都妹有遍历完，谁小就把谁放入sorted数组.
之后要养成编写测试用例的习惯，需要考虑多种极端情况。
代码如下：
vector<int> merge(vector<int> &nums1, int m, vector<int> &nums2, int n)
{
int p1,p2;
int sorted[m + n];
int cur;
vector<int> ans;
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 if(nums1[p1] > nums2[p2])
{
cur = nums2[p2++];
}
sorted[p1 + p2 - 1] = cur;
}
for(int i = 0; i < m + n; i++)
{
ans[i] = sorted[i];
}
return ans;
}
