更快的方法-将2个排序后的数组合并为一个没有重复值的排序后的数组 [英] What is faster - merge 2 sorted arrays into a sorted array w/o duplicate values
问题描述
我试图找出执行以下任务的最快方法：
编写一个函数，该函数接受两个数组作为参数-每个数组都是一个排序后的严格递增的整数数组，并返回一个新的严格递增的整数数组，其中包含两个输入数组中的所有值。
例如。合并[1、2、3、5、7]和[1、4、6、7、8]应该返回[1、2、3、4、5、6、7、8]。
由于我没有接受过正规的编程教育，所以我觉得算法和复杂性有点陌生：)我提供了两种解决方案，但是我不确定哪一种更快。 p>
解决方案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）;
}否则，如果（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）;
有人可以帮我解决这两种解决方案的时间复杂性吗？另外，还有另一种更快的解决方案吗？我应该使用reduce（）吗？
复杂度还取决于您在代码中使用的方法。
1）排序中常用的算法是Quicksort（作为快速排序的变体，是introsort）。
它具有O（ n log n）复杂度，但是如果已经对输入进行排序，最坏的情况可能仍然是O（n ^ 2）。因此，您的解决方案具有O（length（b）+ length（a）+ length（b）log（length（a）+ length（b）））运行时复杂度。
2）根据 splice（）的复杂性上的此问题，最糟糕的javascript函数需要O（n）个步骤（将所有元素复制到大小为n + 1的新数组中）。因此，您的第二个解决方案将数组b的长度乘以在剪接期间复制元素所需的n个步骤以及push（）的时间。
对于在线性时间O（n + m）中有效的良好解决方案，请参考此 Java示例并将其移植（即创建长度为（a）+长度（b）的数组，并通过索引逐步显示）。或在答案下方查看非常紧密甚至更快的实现。
I was trying to figure out which is the fastest way to do the following task:
Write a function that accepts two arrays as arguments - each of which is a sorted, strictly ascending array of integers, and returns a new strictly ascending array of integers which contains all values from both of the input arrays.
Eg. merging [1, 2, 3, 5, 7] and [1, 4, 6, 7, 8] should return [1, 2, 3, 4, 5, 6, 7, 8].
Since I don't have formal programming education, I fint algorithms and complexity a bit alien :) I've came with 2 solutions, but I'm not sure which one is faster.
solution 1 (it actually uses the first array instead of making a new one):
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);
and solution 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);
Can someone help me with time complexity of both solutions? Also, is there another, faster solution? Should I be using reduce()?
The complexity also depends on the methods that you use in your code.
1) An algorithm commonly used for sorting is Quicksort (introsort as a variation of quicksort).
It has O(n log n) complexity however the worst case may still be O(n^2) in case the input is already sorted. So your solution has O( length(b) + length(a)+length(b) log (length(a)+length(b)) ) runtime complexity.
2) According to this question on the complexity of splice() the javascript function needs O(n) steps at worst (copying all elements to the new array of size n+1). So your second solution takes length of array b multiplied by n steps needed to copy the elements during splice plus the time to push().
For a good solution that works in linear time O(n+m) refer to this Java example and port it (i.e. create an array of size length(a) + length(b) and step via the indeces as shown). Or check out the very tight and even a littler faster implementation below of the answer.
这篇关于更快的方法-将2个排序后的数组合并为一个没有重复值的排序后的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
