什么更快——将两个排序的数组合并成一个没有重复值的排序数组

Question

我试图找出哪种是执行以下任务的最快方法：

编写一个函数，接受两个数组作为参数——每个数组都是一个排序的严格升序的整数数组，并返回一个新的严格升序的整数数组，其中包含两个输入数组中的所有值。

例如，合并[1，2，3，5，7]和[1，4，6，7，8]应该返回[1，3，4，5，6，7,8]。

由于我没有受过正规的编程教育，我觉得算法和复杂性有点陌生：）我有两种解决方案，但我不确定哪一种更快。

解决方案 1（它实际上使用第一个数组而不是创建一个新数组）：

function mergeSortedArrays(a, b) {
  for (let i = 0, bLen = b.length; i < bLen; i++) {
    if (!a.includes(b[i])) {
      a.push(b[i])
    } 
  }
  console.log(a.sort());
}

const foo = [1, 2, 3, 5, 7],
      bar = [1, 4, 6, 7, 8];
mergeSortedArrays(foo, bar);

和解决方案2：

function mergeSortedArrays(a, b) {
  let mergedAndSorted = [];

  while(a.length || b.length) {
    if (typeof a[0] === 'undefined') {
      mergedAndSorted.push(b[0]);
      b.splice(0,1);
    } else if (a[0] > b[0]) {
      mergedAndSorted.push(b[0]);
      b.splice(0,1);
    } else if (a[0] < b[0]) {
      mergedAndSorted.push(a[0]);
      a.splice(0,1);
    } else {
      mergedAndSorted.push(a[0]);
      a.splice(0,1);
      b.splice(0,1);
    }
  }
  console.log(mergedAndSorted);
}

const foo = [1, 2, 3, 5, 7],
      bar = [1, 4, 6, 7, 8];
mergeSortedArrays(foo, bar);

有人能帮我解决这两个解决方案的时间复杂度吗？还有，是否有另一个更快的解决方案？我应该使用减少（）吗？

Answer 1

复杂性还取决于您在代码中使用的方法。

1)通常用于排序的算法是Quicksort (introsort是Quicksort的变体)。

它的复杂度为O（n log n），但是在输入已经排序的情况下，最坏的情况可能仍然是O（n^2）。因此，您的解决方案具有O（长度（b）长度（a）长度（b）log（长度（a）长度（b）））运行时复杂度。

2）根据这个关于splice（）复杂性的问题，javascript函数最坏需要O（n）步骤（将所有元素复制到大小为n 1的新数组中）。因此，您的第二个解决方案将数组 b 的长度乘以在拼接期间复制元素所需的 n 步加上 push（） 的时间。

对于在线性时间O（n m）内工作的好的解决方案，请参考此Java示例并将其移植（即创建一个大小-长度（a）-长度（b）的数组，并通过所示的索引步进）。或者看看答案下面非常紧凑甚至更快的实现。

Answer 2

您的第一个函数修改传递的参数，这是错误的做法。您可以通过以下方式完成：

function mergeSortedArrays(a, b) {
    return a.concat(b.filter(el => !a.includes(el))).sort();
}