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是交叉点中元素的数量。

Answer 2

这应该有效：

• 为每个数组创建一个索引
• 如果对于每个数组，相应索引处的元素相同，则将元素添加到结果列表并将每个索引增加一
• 否则增加指向最低元素的索引
• 重复直到超过第一个数组

如果数组可以包含多个数字的实例，这也应该有效，例如数组 (1,1,2,2)，(2,2,3,3) 将导致 (2,2)。

Answer 3

这就是我的想法：创造一个HashMap<Integer, Integer>它会是什么样子numer->hits；遍历所有数组：

• 如果hashMap中存在元素，则增加count(value)，即count++；
• 如果元素不存在，则将 count = 1 写入值

毕竟你将拥有，数字->计数

1->1
2->3
3->2
4->2
5->3

所以你再次遍历 HashMap 并打印 if(value==arrays.lenth)

所以空间是 O(N) 和 O(N) 步。

注意 hashmap 的访问是恒定的时间（yahoooooo）。