题目： 给定两个有序数组，把两个数组合并为一个。
输入： nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出： nums1 = [1,2,2,3,5,6]
方法一：
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = 0, p2 = 0;
int sorted[m + n];
int cur;
while(p1 < m || p2 < n){
if (p1 == m){
cur = nums2[p2++];
} else if(nums1[p1] < nums2[p2]){
cur = nums1[p1++];
} else {
cur = nums2[p2++];
}
sorted[p1+p2-1] = cur;
}
for(int i=0; i != m+n; ++i){
nums1[i] = sorted[i];
}
}
};
复杂度分析
时间复杂度： O(m+n),指针移动单调递增，最多移动m+n次
空间复杂度： O(m+n),需要建立长度为m+n的中间数组sorted
方法二： 直接合并后排序
class Solution {
public:
void 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(), nums2.end());
}
};
复杂度分析
时间复杂度： 套用快速排序的时间复杂度，平均情况为O(m+n)log(m+n)
空间复杂度： 套用快速排序的空间复杂度，平均情况为O(log(m+n))
