算法:有趣的差异算法

Question

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

数学公式

假设你有两个列表,L并且R每一个都含有一些潜在字母元素S.而且,这些列表具有它们按顺序出现的共同元素的属性:也就是说,if L[i] = R[i*]和L[j] = R[j*],然后i< jthen i*< j*.列表根本不需要任何共同元素,并且一个或两个可以是空的.[ 澄清:你可以假设没有重复的元素.]

问题是产生一种列表,这可以被看作是有序对新列表的"差异"的(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

通过遍历两个列表并随时匹配，可以在线性时间内完成区分有序列表。我将尝试在更新中发布一些伪 Java 代码。

由于我们不知道排序算法，并且无法根据小于或大于运算符确定任何排序，因此我们必须将列表视为无序。此外，考虑到结果的格式，您将面临扫描两个列表的情况（至少直到您找到匹配项，然后您可以添加书签并从那里重新开始）。它仍然是 O(n^2) 性能，或者更具体地说是 O(nm)。