自己的写法：对较长的nums1数组使用了双指针法，qp一个在前一个在后，初始时分别指向nums1的第一个元素和第二个元素，分情况讨论有三种，如下代码所示：
代码语言：javascript复制#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
//双指针
int q = 0;
int p = 1;
for (int i = 0; i < n; i )
{
q = 0;
p = 1;
//一共三种情况
//1.插在数组第一个元素前面
if (nums2[i] <=nums1[0])
{
for (int j = m-1; j >= 0; j--)
{
nums1[j 1] = nums1[j];
}
nums1[0] = nums2[i];
m ;
continue;
}
//2.插在数组最后一个元素的后一个位置
if (nums2[i] >= nums1[m - 1])
{
nums1[m] = nums2[i];
m ;
continue;
}
//3.插在快慢指针qp之间
while (p < m)
{
if (nums2[i] <= nums1[p] && nums2[i] > nums1[q])
{
for (int j = m - 1; j >= p; j--)
{
nums1[j 1] = nums1[j];
}
nums1[q 1] = nums2[i];
m ;
break;
}
q , p ;
}
}
}
};
void test()
{
vector<int> v1 = { 1,2,3,0,0,0 };
vector<int> v2 = { 2,5,6 };
Solution s;
s.merge(v1, 3, v2, 3);
for (int i = 0; i < v1.size(); i )
{
cout << v1[i] << " ";
}
}
int main()
{
test();
system("pause");
return 0;
}
参照他人的解法
方法一 : 合并后排序
代码语言：javascript复制class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
//第一步合并两个容器
int j = 0;
for (int i = m; i < m n; i )
{
nums1[i] = nums2[j ];
}
//对合并后的容器进行排序
sort(nums1.begin(), nums1.end());
}
};方法三 : 双指针 / 从后往前
代码语言：javascript复制class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
int i = m n - 1;
m--, n--;
while (n >= 0)
{
while (m >= 0 && (nums1[m] > nums2[n]))
{
nums1[i--] = nums1[m--];
}
nums1[i--] = nums2[n--];
}
}
};
