algorithm - 用 O(n·m) 列出交集

Question

假设我们有两个长度分别为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)

编辑:我们可以假设我们的列表已排序。

Answer 1

对于排序列表，以下算法应该有效:

你可以有 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))