1

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

数组是无序的；公共元素位于不同的位置，但顺序相同（如果在数组 A 中的公共元素b在a之后，则在数组 B 中也会发生同样的情况）并且最大距离为 N。

我不能使用更多 O(N) 的额外空间。

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

这样做的代价应该是，使用m作为数组 B 的长度，O(m N log N)

我尝试过使用哈希表，但为了管理冲突，我必须实现一个列表，效率会下降。

有一个更好的方法？

4

1 回答 1

0

假设您的匹配序列中可以有“洞”（A = [1,3,2] AND 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 中未找到的 A 的下一个元素，而 (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-22T11:20:13.227 回答