在列表中查找共同名称的算法

Question

我一直在阅读 Robert Sedgewick 所著的《算法》一书中的算法，一段时间以来我一直被一个练习问题所困扰。这是问题:

给定 3 个列表，每个列表包含 N 个名称，找到一个算法来确定所有三个列表是否有任何共同的名称。该算法必须具有 O(Nlog^N) 复杂度。您只能使用排序算法，并且唯一可以使用的数据结构是堆栈和队列。

我想我可以使用 HashMap 解决这个问题，但问题限制了我们这样做。即使那样，仍然不会有 Nlog^N 的复杂性。

Answer 1

如果您对每个列表进行排序，那么您可以通过选择列表 A 的名字将其与列表 B 中的名字进行比较，在 O(n) 时间内检查所有三个列表是否有任何 1 个名字，如果是元素 < 列表 A 的元素，弹出列表 b 元素并重复直到列表 B >= 列表 A。如果找到匹配项，则在 C 上重复该过程。如果在 C 中找到匹配项，也返回 true，否则返回下一个a中的元素。

现在您必须在 n log n 时间内对所有列表进行排序。你可以用你最喜欢的排序算法来做，尽管你必须有点创造性地使用堆栈和队列。我可能会推荐归并排序

下面的伪代码有点乱，因为我正在更改我正在迭代的列表

伪代码:假设 listA、b 和 c 是排序的队列，其中最小的名称位于队列的顶部。

eltB = listB.pop()
eltC = listC.pop()
for eltA in listA:
    while(eltB<=eltA):
        if eltB==eltA:                
            while(eltC<=eltB):
                if eltB==eltC:
                    return true
                if eltC<eltB:
                    eltC=listC.pop();
        eltB=listB.pop()