题目链接规定了时间我首先想到的是归并排序以时间换空间题目要求时间复杂度O(mn)提示nums1.length m n nums2.length n 0 m, n 200 1 m n 200 -109 nums1[i], nums2[j] 109而且这个题理论上是合并所以得把最后合并的结果放到nums1[]上下面是代码classSolution{public:voidmerge(vectorintnums1,intm,vectorintnums2,intn){vectorinttemp(nums1.begin(),nums1.begin()m);intp0;intp10;intp20;while(p1mp2n){if(temp[p1]nums2[p2])nums1[p]temp[p1];elsenums1[p]nums2[p2];}while(p1m)nums1[p]temp[p1];while(p2n)nums1[p]nums2[p2];}};然后再复习一下归并排序这么多年了发现自己学习算法过于死板其实归并排序是一棵归并排序二叉树。那么一涉及到树就很容易理解这里头有递归所以归并排序是由递归和merge函数组合来实现的那个大的递归函数就是voidmergeSort(vectorintarr,intl,intr){if(lr)returnintmid(lr)/2;mergesort(arr,l,mid);mergesort(arr,mid,r);merge(arr,l,mid,r);}下面是完整的归并排序的代码#includeiostream#includevectorusing namespace std;// 合并两个有序区间 [l, mid] 和 [mid1, r]voidmerge(vectorintarr,intl,intmid,intr){vectorinttemp(r-l1);intil;intjmid1;intk0;while(imidjr){if(arr[i]arr[j]){temp[k]arr[i];}else{temp[k]arr[j];}}while(imid)temp[k]arr[i];while(jr)temp[k]arr[j];// 复制回原数组for(intp0;ptemp.size();p){arr[lp]temp[p];}}// 归并排序递归voidmergeSort(vectorintarr,intl,intr){if(lr)return;intmid(lr)/2;mergeSort(arr,l,mid);mergeSort(arr,mid1,r);merge(arr,l,mid,r);}intmain(){vectorintarr{5,2,9,1,5,6,3,8};cout排序前;for(intx:arr)coutx ;coutendl;mergeSort(arr,0,arr.size()-1);cout排序后;for(intx:arr)coutx ;coutendl;return0;}直接从后面替换插入的方法classSolution{public:voidmerge(vectorintnums1,intm,vectorintnums2,intn){intinums1.size()-1;n--;m--;while(n0){while(m0nums1[m]nums2[n]){swap(nums1[i--],nums1[m--]);}swap(nums1[i--],nums2[n--]);}}};