88.Merge Sorted Array
88.Merge Sorted Array
难度: Easy
给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。 说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
示例:
1
输入:
2
nums1 = [1,2,3,0,0,0], m = 3
3
nums2 = [2,5,6], n = 3
4
输出: [1,2,2,3,5,6]
Copied!
方法: 题目比较简单。最直观的就是新建一个nums1的长度的向量放最后合并的数组,不过会增加一些空间复杂度。 代码如下:
1
class Solution {
2
public:
3
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
4
vector<int> tmp=nums1;
5
int N=nums1.size();
6
int n1=0,n2=nums2.size();
7
for(int i=N-1;i>=0;i--)
8
if(nums1[i]){
9
n1=i+1;
10
break;
11
}
12
int s1=0,s2=0;
13
while(s1<n1 && s2 <n2)
14
{
15
if(tmp[s1]<=nums2[s2])
16
{
17
nums1[s1+s2]=tmp[s1];
18
++s1;
19
}
20
else
21
{
22
nums1[s1+s2]=nums2[s2];
23
++s2;
24
}
25
}
26
if(s1 == n1 && s2<n2)
27
for(;s2<n2;++s2)
28
nums1[s1+s2]=nums2[s2];
29
if(s2==n2 && s1<n1)
30
for(;s1<n1;++s1)
31
nums1[s1+s2]=tmp[s1];
32
33
34
}
35
};
Copied!
这题并没有用到m和n,因为m和n本可以计算出来,即代码中的n1和n2。
另一种方法:直接原地操作,因为nums1后面空间较大,所以逆向合并即可。 代码如下:
1
class Solution {
2
public:
3
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
4
int s1=m-1,s2=n-1;
5
for(int i=m+n-1;i>=0;--i)
6
{
7
if(s1>=0 && s2>=0)
8
{
9
if(nums1[s1]<nums2[s2])
10
{
11
nums1[i]=nums2[s2];
12
--s2;
13
}
14
15
else
16
{
17
nums1[i]=nums1[s1];
18
--s1;
19
}
20
}
21
else
22
break;
23
}
24
if(s1<0 && s2<0)
25
return ;
26
else if(s1<0)
27
{
28
for (int i=s2;i>=0;i--)
29
{
30
nums1[i]=nums2[i];
31
}
32
}
33
34
35
}
36
};
Copied!
Copy link