这道题其实比较简单，通过依次比较大小并且按顺序大小放入到一个数组中即可，但是由于最终要放到原数组中，这里比较麻烦。一种比较简单的做法是另外开辟一块空间，然后在合并之后再复制一遍，如下所示。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
vector<int> temp(m+n, 0);
int i1 = 0, i2 = 0, cur = 0;
while(i1 < m && i2 < n){
if(nums1[i1] <= nums2[i2])
temp[cur++] = nums1[i1++];
else
temp[cur++] = nums2[i2++];
}
while(i1 < m) temp[cur++] = nums1[i1++];
while(i2 < n) temp[cur++] = nums2[i2++];
for(int i=0; i<m+n; i++){
nums1[i] = temp[i];
}
}
};
空间复杂度O(m+n)，时间复杂度O(n)。提交之后，看了别人的解法，发现从后边开始时不需要额外开辟数组，如下所示。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i1 = m-1, i2 = n-1, cur = m+n-1;
while(i1 >= 0 && i2 >= 0){
if(nums1[i1] >= nums2[i2])
nums1[cur--] = nums1[i1--];
else
nums1[cur--] = nums2[i2--];
}
while(i1 >= 0) nums1[cur--] = nums1[i1--];
while(i2 >= 0) nums1[cur--] = nums2[i2--];
}
};
这种思维的确十分精巧，而且这种思想在操作系统内存管理中有用到。
