欢迎访问LeetCode题解合集
题目描述
给你两个有序整数数组 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 \le m, n \le 200$
-
$1 \le m + n \le 200$
-
$-10^9 \le nums1[i], nums2[i] \le 10^9$
题解:
有序数组的二路归并。
法一:
如果我们考虑从前往后进行合并,那么就有可能覆盖掉 nums1
中原有元素,这就意味着我们需要额外开辟一个数组来保存合并结果。
时间复杂度:$O(n + m)$
额外空间复杂度:$O(n + m)$
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
vector<int> c( n + m );
int k = 0;
for ( int i = 0, j = 0; i < m || j < n; ) {
if ( i < m && j < n ) {
if ( nums1[i] <= nums2[j] ) c[k++] = nums1[i++];
else c[k++] = nums2[j++];
} else if ( i < m ) c[k++] = nums1[i++];
else c[k++] = nums2[j++];
}
nums1 = c;
}
};
/*
时间:0ms,击败:100.00%
内存:9MB,击败:71.34%
*/
法二:
其实不开辟额外数组也是可以的,因为题目中说明了 nums1
的空间等于 m + n
,那么我们可以从后往前合并,放置的元素位置从 m + n - 1
开始即可。
时间复杂度:$O(n + m)$
额外空间复杂度:$O(1)$
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int k = m + n - 1;
for ( int i = m - 1, j = n - 1; i >= 0 || j >= 0; ) {
if ( i >= 0 && j >= 0 ) {
if ( nums1[i] >= nums2[j] ) nums1[k--] = nums1[i--];
else nums1[k--] = nums2[j--];
} else if ( i >= 0 ) nums1[k--] = nums1[i--];
else if ( j >= 0 ) nums1[k--] = nums2[j--];
}
return;
}
};
/*
时间:0ms,击败:100.00%
内存:8.8MB,击败:88.71%
*/