假设我们有两个长度分别为n和m的列表:
val l1 = Seq(1,2,3,4,5,6,7,8,9,0)
val l2 = Seq(2,4,6,8,10,12)
有没有办法用小于 O(n·m) 计算它们的交集?
也就是
val result = Seq(2,4,6,8)
编辑:我们可以假设我们的列表已排序。
最佳答案
对于排序列表,以下算法应该有效:
你可以有 2 个指针说 (i 和 j),一个在 l1,另一个在 l2。
现在你可以迭代 l1 和 l2 这样
while (i< l1.size && j < l2.size ) {
if l1[i] < l2[j]
i++
else if (l1[i] == l2[j] )
i++; j++; output = output U {l1[i]}
else
j++
}
这应该是 O(max(m,n))
关于algorithm - 用 O(n·m) 列出交集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46454261/