本文最后更新于 408 天前,其中的信息可能已经有所发展或是发生改变。
一、题述
给你两个有序整数数组 nums1
和 nums2
,请你将 nums2
合并到 nums1
中,使 nums1
成为一个有序数组。
初始化 nums1
和 nums2
的元素数量分别为 m
和 n
。你可以假设 nums1
的空间大小等于 m + n
,这样它就有足够的空间保存来自 `nums2` 的元素。
示例 1:
输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
示例 2:
输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
提示:
- nums1.length == m + n
- nums2.length == n
- 0 <= m, n <= 200
- 1 <= m + n <= 200
- -109 <= nums1[i], nums2[i] <= 109
二、题解
1、直接法
我们可以直接把两个数组拼接起来,然后用sort函数对整合后的数组进行一个排序。
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(),nums1.end()); //STL排序
}
};
复杂度分析
- 时间复杂度:O((m+n)\log(m+n))O((m+n)log(m+n))。
快速排序、序列长度为 m+nm+n。
- 空间复杂度:O(\log(m+n))O(log(m+n))。
快速排序、序列长度为 m+nm+n。
2、双指针
由于题目中给的两个数组序列是已经排序好的,所以我们可以用双指针的办法,对两数组进行按序组合。
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 temp;
while (p1 < m || p2 < n) {
if (p1 == m) {
temp = nums2[p2++];
} else if (p2 == n) {
temp = nums1[p1++]; //当有一方到头时直接将后半段拼接
} else if (nums1[p1] < nums2[p2]) {
temp = nums1[p1++];
} else {
temp = nums2[p2++];
}
sorted[p1 + p2 - 1] = temp;
}
for (int i = 0; i != m + n; ++i) {
nums1[i] = sorted[i]; //数组赋值
}
}
};
复杂度分析
- 时间复杂度:O(m+n)。
指针移动单调递增,最多移动 m+n 次,因此时间复杂度为 O(m+n)。
- 空间复杂度:O(m+n)。
建立长度为 m+n 的中间数组。
3、逆向双指针(Leetcode解答)
2中,为防止 nums1
中的变量被覆盖,所以我们采用新建一个临时变量的方法以规避这一问题。但同时的,我们也可以采用逆向的方法,可以将指针设置为从后向前遍历,每次取两者之中的较大者放进 nums1
的最后面,从后向前覆盖。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = nums1.size();
while (n > 0) {
if (m > 0 && nums1[m-1] > nums2[n-1]) {
nums1[--i] = nums1[--m];
}else{
nums1[--i] = nums2[--n]; //先自减后操作
}
}
}
};
复杂度分析
- 时间复杂度:O(m+n)。
指针移动单调递减,最多移动m+n
次,因此时间复杂度为 O(m+n)。
- 空间复杂度:O(1)。
直接对数组nums1
原地修改,不需要额外空间。