algorithm - 加入有序数组的最佳方法是什么？

Question

我有几个整数数组。每个数组中的元素都是有序的。数组没有重复项。

我需要将所有数组合并为一个，这样生成的数组只包含每个数组中存在的元素。

比如我有数组

(1,2,3,4,5)(2,3,5)(1,2,4,5)

结果必须是 (2,5)

实现最佳性能的最佳方法是什么？

Answer 1

如果预期数组包含许多不同的数字，并且所有数组中只出现几个，

• 选择两个最小的数组，通过顺序遍历它们来计算它们的交集(就像合并排序一样)，O(len1 + len2)
• 虽然并非所有数组都已被扫描，但选择下一个最小的数组，并计算其与先前处理的数组的交集的交集，使用顺序扫描 if length(intersection)*log(length(array)) >= length(array)，否则在array中查找交集的元素。

最坏情况下的复杂度是 O(sum(lengths))，如果幸运的话，你可以得到 k * sum(log(length))，其中 k是交集的元素个数。