日复一日的生活里也会有新的快乐
—— 24.3.27
合并两个有序数组
给你两个按 非递减顺序 排列的整数数组
nums1
和nums2
,另有两个整数m
和n
,分别表示nums1
和nums2
中的元素数目。请你 合并
nums2
到nums1
中,使合并后的数组同样按 非递减顺序 排列。(next[data]>=data)注意:最终,合并后数组不应由函数返回,而是存储在数组
nums1
中。为了应对这种情况,nums1
的初始长度为m + n
,其中前m
个元素表示应合并的元素,后n
个元素为0
,应忽略。nums2
的长度为n
。
方法一:直接合并后排序
最直观的方法是先将数组 nums2放进数组 nums1的尾部,然后直接对整个数组进行排序。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
for (int i = 0; i != n; i++) {
nums1[m + i] = nums2[i];
}
Arrays.sort(nums1);
}
}
复杂度分析
时间复杂度:O((m+n)log(m+n))。
排序序列长度为 m+n,套用快速排序的时间复杂度即可,平均情况为 O((m+n)log(m+n))。空间复杂度:O(log(m+n))
排序序列长度为 m+n,套用快速排序的空间复杂度即可,平均情况为 O(log(m+n))
方法二:双指针方法
方法一没有利用数组 nums1与 nums2已经被排序的性质。为了利用这一性质,我们可以使用双指针方法。这一方法将两个数组看作队列,每次从两个数组头部取出比较小的数字放到结果中。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = 0, p2 = 0;
int[] sorted = new int[m + n];
int cur;
while (p1 < m || p2 < n) {
# 如果数组1达到最大长度,则合并后总的数组3的新元素等于数组2p2++位置的元素
if (p1 == m) {
cur = nums2[p2++];
} else if (p2 == n) {
# 如果数组2达到最大长度,则合并后总的数组3的新元素等于数组1p1++位置的元素
cur = nums1[p1++];
} else if (nums1[p1] < nums2[p2]) {
# 如果数组1,2都未达到最大长度,则合并后总的数组3的新元素等于数组1的p1位置元素和数组2p2位置元素的较小值
cur = nums1[p1++];
} else {
cur = nums2[p2++];
}
# 最终新数组长度发生改变
sorted[p1 + p2 - 1] = cur;
}
# 将合并后的新数组赋值到数组1中,不用返回,但是存在数组1的地址中
for (int i = 0; i < m + n; ++i) {
nums1[i] = sorted[i];
}
}
}
复杂度分析
时间复杂度:O(m+n)。
指针移动单调递增,最多移动 m+nm+nm+n 次,因此时间复杂度为 O(m+n)。空间复杂度:O(m+n)。
需要建立长度为 m+nm+nm+n 的中间数组 sorted。
方法三:逆向双指针
双指针数组元素从后向前比较,我们在把大的值放入nums1中时,如果放的是nums1,则nums1空出一个位置 放的是nums2时,才会占位置,而空出的位置刚好是够nums2用的
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int a = m - 1, b = n - 1, c = m + n - 1;
while (a >= 0 && b >= 0) {
nums1[c--] =(nums1[a] > nums2[b] ? nums1[a--] : nums2[b--]);
}
while (a >= 0) {
nums1[c--] = nums1[a--];
}
while (b >= 0) {
nums1[c--] = nums2[b--];
}
}
}
复杂度分析
标签:16,int,复杂度,力扣,++,数组,一题,nums1,nums2 From: https://blog.csdn.net/m0_73983707/article/details/137051830时间复杂度:O(m+n)。
指针移动单调递减,最多移动 m+n 次,因此时间复杂度为 O(m+n)。空间复杂度:O(1)。
直接对数组 nums1 原地修改,不需要额外空间。