我有一个整数数组列表，其中每个数组都有一些排序的数字。在这里，我想找到基于所有数组的最常出现的整数序列组合。例如数组列表如下
A1 - 1 2 3 5 7 8
A2 - 2 3 5 6 7
A3 - 3 5 7 9
A4 - 1 2 3 7 9
A5 - 3 5 7 10
这里
{3,5,7} - {A1,A3,A5}
{2,3} - {A1,A2,A4}
因此我们可以将 {3,5,7} 或 {2,3} 作为最常出现的组合。
现在我使用的算法如下
找到一个集合与所有其他集合的交集。并存储结果集。如果它已经存在，则增加结果集的出现。 例如: 找到以下所有的交集
A1 intersection A2
A1 intersection A3
A1 intersection A4
A1 intersection A5
A2 intersection A3
A2 intersection A4
A2 intersection A5
A3 intersection A4
A3 intersection A5
A4 intersection A5
此处A1交集A3与A3交集A5相同，因此set-{3,5,7}的出现次数可以设置为2。 同样，可以确定每个结果集的出现。
但是这个算法需要 O(n^2) 的复杂度。 假设每个集合都已排序，我很确定我们可以找到一个更好的算法，复杂度为 O(n)，我无法记下。 谁能建议一个 O(n) 算法。
最佳答案
如果你有一个长度为 n 的序列，那么它的前缀长度为 n-1 并且出现的频率至少为 - 退化的大小写是最常见的字符，它是长度为 1 的序列至少出现的频率为作为任何更长的序列。您是否有感兴趣的最小后缀长度？
不管怎样，一个想法是连接所有的序列，用在其他地方出现的不同整数分隔它们，然后计算 http://en.wikipedia.org/wiki/Suffix_array在线性时间内。一次通过后缀数组应该可以让你找到任何给定长度的最常见的子序列——它不应该跨越两个不同数组之间的间隙，因为每个这样的长度为 n 的序列都是唯一的，因为分隔数组的字符是独特的。 (另见 http://en.wikipedia.org/wiki/LCP_array)
关于algorithm - 最常出现的组合，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15187745/