请实现下面的 mergeArray 方法
参考答案
题目意图
合并两个有序数组并保持有序。
实现一:双指针(推荐,O(n+m))
function mergeArray(a: number[], b: number[]): number[] {
const res: number[] = [];
let i = 0, j = 0;
while (i < a.length && j < b.length) {
if (a[i] <= b[j]) res.push(a[i++]);
else res.push(b[j++]);
}
while (i < a.length) res.push(a[i++]);
while (j < b.length) res.push(b[j++]);
return res;
}
实现二:原地合并(a 预留空间,LeetCode 88 风格)
function mergeInPlace(a: number[], m: number, b: number[], n: number): void {
let i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
a[k--] = (i >= 0 && a[i] > b[j]) ? a[i--] : b[j--];
}
}
必须从后往前,否则会覆盖 a 中尚未比较的元素。
实现三:合并去重
function mergeUnique(a: number[], b: number[]): number[] {
const m = mergeArray(a, b);
return m.filter((v, i) => i === 0 || v !== m[i - 1]);
}
关键点
- 每次取较小者;相等时取
a可保证稳定性。 - 一个数组耗尽后,剩余元素直接搬运,不必继续比较。
- 输入前提是已排序;数字排序要传比较器
(x, y) => x - y,默认sort是字典序。 - 泛型版加比较函数更通用:
mergeArray<T>(a: T[], b: T[], cmp: (x: T, y: T) => number)。 - 多个有序数组用最小堆多路归并,复杂度
O(N log k)。
复杂度
时间 O(n+m),空间 O(n+m)(新建结果数组);原地版空间 O(1)。