1

我一直在阅读 Robert Sedgewick 所著的 Algorithms 一书中的 Algorithms，并且我一直被困在一个锻炼问题上。这是问题：

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

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

4

2 回答 2

3

如果您对每个列表进行排序，那么您可以通过选择列表 A 的第一个名称将其与列表 B 中的第一个名称进行比较，如果该元素为 <对于列表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()
于 2012-09-28T17:02:50.413 回答
0

脚步：

  1. 使用O(N lgN)排序算法对三个列表进行排序。
  2. 从每个列表中弹出一项。
  3. 如果您尝试从中弹出的任何列表为空，那么您就完成了，即不存在公共元素。
  4. 否则，比较三个元素。
  5. 如果元素相等，你就完成了——你找到了共同的元素。
  6. 否则，保留三个元素中的最大值（恒定时间）并从丢弃两个元素的相同列表中进行补充。
  7. 转到第 3 步。

第 1 步O(N lgN)执行，其余步骤执行O(N)，因此总体复杂性为O(N lgN).

于 2012-09-29T01:48:29.577 回答