算法 : Interesting diffing algorithm

Question

这是在现实世界中出现的，我想我会分享它，因为它可能会导致一些有趣的解决方案。本质上，该算法需要区分两个列表，但让我给你一个更严格的问题定义。

数学公式

假设您有两个列表，L 和 R，每个列表都包含来自某个底层字母表 S 的元素。此外，这些列表具有它们所具有的公共(public)元素按顺序出现的属性:也就是说，如果 L[i] = R[i*] 和 L[j] = R[j*], i <j 然后 i* <j*。这些列表根本不需要任何公共(public)元素，并且一个或两个可以为空。 [澄清:您可以假设元素没有重复。]

问题是产生一种列表的“差异”，它可以被视为有序对 (x,y) 的新列表，其中 x 是L 和 y 来自 R，具有以下属性:

1. 如果 x 出现在两个列表中，则 (x,x) 出现在结果中。
2. 如果x出现在L中，但没有出现在R中，那么(x,NULL)出现在结果。
3. 如果y出现在R中，但没有出现在L中，那么(NULL,y)出现在结果。

最后

• 结果列表与每个输入列表具有“相同”的排序:粗略地说，它与每个列表共享与上述相同的排序属性(参见示例)。

例子

L = (d)
R = (a,b,c)
Result = ((NULL,d), (a,NULL), (b,NULL), (c,NULL))

L = (a,b,c,d,e)  
R = (b,q,c,d,g,e)
Result = ((a,NULL), (b,b), (NULL,q), (c,c), (d,d), (NULL,g), (e,e))

有没有人有好的算法来解决这个问题？复杂度如何？

Answer 1

如果您愿意在不同的数据结构中复制其中一个列表，则有一种方法可以在 O(n) 中执行此操作。这是经典的时间/空间权衡。

创建列表R的 HashMap ，键是元素，值是数组的原始索引；在 C++ 中，您可以使用来自 tr1 或 boost 的 unordered_map。

保留列表 R 的未处理部分的索引，初始化为第一个元素。

对于列表 L 中的每个元素，检查 HashMap 以查找列表 R 中的匹配项。如果没有找到，则输出 (L value, NULL)。如果匹配，则从 HashMap 中获取相应的索引。对于列表 R 中直到匹配索引的每个未处理元素，输出(NULL，R 值)。对于匹配，输出(值，值)。

当您到达列表 L 的末尾时，遍历列表 R 的剩余元素并输出(NULL，R 值)。

编辑: 这是 Python 中的解决方案。对于那些说此解决方案取决于是否存在良好的散列函数的人来说——当然是这样。如果这是一个问题，原始发布者可能会为问题添加额外的限制，但在那之前我会持乐观态度。

def FindMatches(listL, listR):
    result=[]
    lookupR={}
    for i in range(0, len(listR)):
        lookupR[listR[i]] = i
    unprocessedR = 0
    for left in listL:
        if left in lookupR:
            for right in listR[unprocessedR:lookupR[left]]:
                result.append((None,right))
            result.append((left,left))
            unprocessedR = lookupR[left] + 1
        else:
            result.append((left,None))
    for right in listR[unprocessedR:]:
        result.append((None,right))
    return result

>>> FindMatches(('d'),('a','b','c'))
[('d', None), (None, 'a'), (None, 'b'), (None, 'c')]
>>> FindMatches(('a','b','c','d','e'),('b','q','c','d','g','e'))
[('a', None), ('b', 'b'), (None, 'q'), ('c', 'c'), ('d', 'd'), (None, 'g'), ('e','e')]