Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
- The number of elements initialized in nums1 and nums2 are m and n respectively.
- You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.
Example:
1
2
3
4
5
| Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
|
Constraints:
-10^9 <= nums1[i], nums2[i] <= 10^9nums1.length == m + nnums2.length == n
1 归并排序1
简单的归并排序, 分类讨论即可, 注意nums1或nums2中元素用光的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
vector<int> num1 = nums1;
int k = 0;
int i = 0;
int j = 0;
while(i < m || j < n)
{
if(i == m)
{
nums1[k++] = nums2[j++];
}
else if(j == n)
{
nums1[k++] = num1[i++];
}
else
{
if(num1[i] < nums2[j])
{
nums1[k++] = num1[i++];
}
else
{
nums1[k++] = nums2[j++];
}
}
}
}
};
|
2 归并排序2
归并排序1需要使用额外空间, 这次从nums1的末尾开始插入, 不需要额外空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int k = m + n - 1;
int j = n - 1;
int i = m - 1;
while(k >= 0)
{
if(j < 0)
{
nums1[k--] = nums1[i--];
}
else if(i < 0)
{
nums1[k--] = nums2[j--];
}
else
{
if(nums1[i] > nums2[j])
{
nums1[k--] = nums1[i--];
}
else
{
nums1[k--] = nums2[j--];
}
}
}
}
};
|