在两个不同大小的数组中寻找共同元素

我必须找到获得两个不同大小数组的公共元素的最佳方法。在两个不同大小的数组中寻找共同元素

这些数组是无序的;共同要素是在不同的位置上，但以相同的顺序（如果阵列中的一个共同的元件b一个之后来到，相同的数组B中发生的），并与最大距离N.

我不能t使用更多的O（N）空间。

实际上，我从数组A中提取N个元素，使用mergesort对它们进行排序，并使用数组B的N个元素执行双子集搜索。然后从我找到的匹配位置获取下一个N元素并执行另一个循环。

这样做的成本应，使用米作为阵列B的长度，O（m×n个对数N）

我曾尝试使用散列表，但管理碰撞我要实现一个列表，效率下降。

还有更好的办法吗？

来源

2013-08-22 Marco Fedele

假设你可以在你的匹配序列 “洞”（A = [1,3,2]和B = [1,4,2]然后MatchSet = {1,2}）

也许我我错了，但你可以尝试这样的伪代码：

i <- 0; j <- 0; jHit <- -1 
matchSet <- Empty 
While i < Length(A) AND j < Length(B): 
    If A[i] == B[j] Then 
     matchSet.add(A[i]) 
     i <- i+1 
     jHit <- j 
    End If 
    j <- j+1 
    If j == Length(B) Then 
     i <- i+1 
     j <- jHit+1 
    End If 
End Loop

第一个索引（i）指向的下一个元素B中没有发现，而（j）是用来寻找B的下一个元素（后在A中找到的最后一个元素）。

这可以给你O（mN）和O（N）空间使用的时间复杂度。

这里有一个实施的Python：

def match(A,B): 
    i = 0 
    j = 0 
    jHit = -1 
    res = [] 
    while i < len(A) and j < len(B): 
     if A[i] == B[j]: 
      res.append(A[i]) 
      i += 1 
      jHit = j 
     j += 1 
     if j == len(B): 
      i += 1 
      j = jHit+1 
    return res

来源

2013-08-22 11:20:13

在两个不同大小的数组中寻找共同元素

回答

相关问题