难度: Easy
给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。 说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
示例:
输入:nums1 = [1,2,3,0,0,0], m = 3nums2 = [2,5,6], n = 3输出: [1,2,2,3,5,6]
方法: 题目比较简单。最直观的就是新建一个nums1的长度的向量放最后合并的数组,不过会增加一些空间复杂度。 代码如下:
class Solution {public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {vector<int> tmp=nums1;int N=nums1.size();int n1=0,n2=nums2.size();for(int i=N-1;i>=0;i--)if(nums1[i]){n1=i+1;break;}int s1=0,s2=0;while(s1<n1 && s2 <n2){if(tmp[s1]<=nums2[s2]){nums1[s1+s2]=tmp[s1];++s1;}else{nums1[s1+s2]=nums2[s2];++s2;}}if(s1 == n1 && s2<n2)for(;s2<n2;++s2)nums1[s1+s2]=nums2[s2];if(s2==n2 && s1<n1)for(;s1<n1;++s1)nums1[s1+s2]=tmp[s1];}};
这题并没有用到m和n,因为m和n本可以计算出来,即代码中的n1和n2。
另一种方法:直接原地操作,因为nums1后面空间较大,所以逆向合并即可。 代码如下:
class Solution {public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int s1=m-1,s2=n-1;for(int i=m+n-1;i>=0;--i){if(s1>=0 && s2>=0){if(nums1[s1]<nums2[s2]){nums1[i]=nums2[s2];--s2;}else{nums1[i]=nums1[s1];--s1;}}elsebreak;}if(s1<0 && s2<0)return ;else if(s1<0){for (int i=s2;i>=0;i--){nums1[i]=nums2[i];}}}};