/**
* 解法一:JS Sort
* 思路:
* (1)先判断 B 为空直接 return,A 为空则将 B shift 到 A 中
* (2)将 B shift 填到 A 尾部的扩容区域,然后用 sort 排序
* 时间复杂度:O(nlogn), JS sort 方法基于快速排序实现
* 空间复杂度:O(1),常数级变量,无额外空间
*/
export function merge(A: number[], m: number, B: number[], n: number) {
if (!B.length || !n) return
for (let i = m; i < m + n; i++) {
A[i] = B.shift()
}
// 升序排列
A.sort((a, b) => a - b)
}
/**
* 解法二:双指针
* 思路:
* (1)先判断 B 为空直接 return,A 为空则将 B shift 到 A 中
* (2)使用三个指针,aIndex 指向数组 A 的最大元素,bIndex 指向数组B的最大元素,mIndex 指向数组A空间的结尾处。
* (3)从两个数组最大的元素开始遍历,直到某一个结束,每次取出较大的一个值放入数组 A 空间的最后,然后指针依次往前。
* (4)如果数组 B 先遍历结束,数组 A 前半部分已经存在了,不用管;但是如果数组 A 先遍历结束,则需要把数组 B 剩余的前半部分依次逆序加入数组 A 前半部分
* 时间复杂度:O(m + n),最坏情况遍历整个数组 A 和 数组 B
* 空间复杂度:O(1),常数级变量,无额外空间
*/
export function merge(A: number[], m: number, B: number[], n: number) {
if (!B.length || !n) return
if (!A.length || !m) {
for (let i = 0; i < n; i++) {
A[i] = B.shift()
}
}
let aIndex: number = m - 1 // 指向数组 A 的结尾
let bIndex: number = n - 1 // 指向数组 B 的结尾
let mIndex: number = m + n - 1 // 指向数组 A 空间的结尾
while (aIndex >= 0 && bIndex >= 0) {
if (A[aIndex] >= B[bIndex]) {
A[mIndex--] = A[aIndex--]
} else {
A[mIndex--] = B[bIndex--]
}
// 数组 A 遍历完,B 还有
if (aIndex < 0) {
while (bIndex >= 0) {
A[mIndex--] = B[bIndex--]
}
}
}
}
一站式解决前端面试高频算法题