合并排序的数组

给定两个排序后的数组 A 和 B,其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法,将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。

示例:

输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3

输出: [1,2,2,3,5,6]
说明:

A.length == n + m

想不出给出的多余空间怎么用 又用赖皮做法先做出来了

1
2
3
4
5
6
7
8
class Solution {
public void merge(int[] A, int m, int[] B, int n) {
for(int a = m,b=0;a<m+n;a++,b++){
A[a]=B[b];
}
Arrays.sort(A);
}
}

题解

后面的空间可以用来逆向双指针 ,这样把最大的数字放在最后面就不会出现数字被覆盖的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public void merge(int[] A, int m, int[] B, int n) {
int pa = m - 1, pb = n - 1;
int tail = m + n - 1;
int cur;
while (pa >= 0 || pb >= 0) {
if (pa == -1) {
cur = B[pb--];
} else if (pb == -1) {
cur = A[pa--];
} else if (A[pa] > B[pb]) {
cur = A[pa--];
} else {
cur = B[pb--];
}
A[tail--] = cur;
}
}
}

复杂度分析

时间复杂度:O(m+n)。
指针移动单调递减,最多移动 m+n 次,因此时间复杂度为 O(m+n)。

空间复杂度:O(1)。
直接对数组 A 原地修改,不需要额外空间。

来源:力扣(LeetCode)