今天在抖音上看到一个这样的题目，好像很多地方都见过，比较基础，提供一些可能高效的解决思路，在算法选择最优解的基础上，继续优化代码细节，让效率快2-3倍，并进行扩展应用。

题目

现有两个有序数组，例如

js
const a = [1, 3, 5];
const b = [2, 4, 6];

需要实现一个函数，将这两个有序数组按元素大小进行合并吗，得到以下结果

js
[1, 2, 3, 4, 5, 6];

解决思路

看着好像蛮简单的，思路可能也很多。在工作里面，如果不考虑效率，可能就这样做了。

js
function mergeArr (a, b) {
    return [...a, ...b].sort((a, b) => a - b);
}

这样，不能说没得到解决，但是在面试里如果这样写，基本是等于没写。

方案

我建议是用双指针的形式来写。

双指针遍历（时间复杂度 O(m+n)）

• 使用两个指针分别遍历两个数组
• 每次选择较小的元素推入结果数组
• 仅需遍历 m + n - 1 次比较（m 和 n 分别为数组长度）

然后因为这两个数组可能长度不是对等的，会导致有数组存在剩余元素的情况。

剩余元素处理（时间复杂度 O(k)）

• 当任一数组遍历完成后，通过 slice 直接获取剩余元素
• 由于两个数组本身已排序，剩余元素可以直接拼接

代码

js

function mergeSortedArrays(a, b) {
  const merged = [];
  let i = 0, j = 0;
  
  while (i < a.length && j < b.length) {
    a[i] <= b[j] ? merged.push(a[i++]) : merged.push(b[j++]);
  }
  
  return merged.concat(a.slice(i)).concat(b.slice(j));
}

在这个场景下，这种写法应该是性能最优的。

不同算法思路的对比

方法	时间复杂度	空间复杂度	适用场景
双指针	O(m+n)	O(m+n)	已排序数组合并
快速排序	O((m+n)log(m+n))	O(m+n)	未排序数组合并
插入排序	O(mn)	O(1)	小规模数组合并

进阶优化(内存预分配)

在之前算法的基础上，可以在很多更细节的角度来优化性能，毕竟在面试中，100分的人就是比99分的人更有机会。

js
function mergeSortedArraysPlus(a, b) {
  const totalLength = a.length + b.length;
  const merged = new Array(totalLength);
  let i = 0, j = 0, k = 0;

  while (i < a.length && j < b.length) {
    merged[k++] = a[i] <= b[j] ? a[i++] : b[j++];
  }

  while (i < a.length) merged[k++] = a[i++];
  while (j < b.length) merged[k++] = b[j++];

  return merged;
}

优化点：

• 预先分配结果数组内存（减少动态扩容开销）
• 使用索引直接赋值（避免 push 方法和 contact 方法的调用开销）

通过实际的数据测试中，进阶优化的版本会比原版本快2-3倍。

几个小细节的优化就在算法思路不变的前提下，性能又强了2-3倍...fucking crazy

扩展应用

在面试中，往往面试官都喜欢在一个角度追着问。既然题目是合并两个有序数组，那如果是合并多个有序数组呢。

思维开阔一点，就能很快get到原理其实没变，可以借助现有JS方法一行代码实现。

js
function mergeKSortedArrays(arrays) {
  return arrays.reduce(mergeSortedArraysPlus, []);
}

mergeSortedArraysPlus就是上面进阶优化版本的实现函数。