最快和最有效的方法来查找2个堆栈的交集

Question

面试问题：找到2个堆栈的交点。在python堆栈中，基本上只是具有pop和push函数的列表。相交是两个堆栈中相同的第一个项目（之后的所有以下值也都相同）现在，我在考虑首先确定它们的长度是否相同，如果不相同，则将较长堆栈的前几个元素切掉。def intersect(s1, s2):        diff = abs(len(s1) - len(s2))        if diff > 0:            for i in range diff:                s1.pop()        else:              while s1[0] != s2[0]:                first = s1.pop()                second = s2.pop()                if compare(first, second) == True #use a comparator func to see if they're equal                   return first否则，除了以线性顺序同时弹出两个堆栈的项目并比较项目外，我想不出更好的方法。我正在寻找带有解释的编码解决方案！谢谢

Answer 1

集合非常快，您可以只使用一个集合

考虑一下

In [51]: class Stack(list):

    ...:     def push(self, x):

    ...:         self.insert(0,x)

    ...:     def pop(self):      

    ...:         return list.pop(self, 0)

    ...:

    ...:

In [52]: a = Stack()

In [53]: a.push(5)

In [54]: a

Out[54]: [5]

In [55]: a.pop()

Out[55]: 5

In [56]: a

Out[56]: []

In [57]: b = Stack()

In [58]: a.push(1)

In [59]: a.push(2)

In [60]: a.push(3)

In [61]: a.push(4)

In [62]: b.push(2)

In [63]: b.push(3)

In [64]: b.push(4)

In [65]: b.push(5)

In [66]: a_s = set()

In [67]: b_s =set()

In [68]: while a != []:

    ...:     a_s.add(a.pop())

    ...:

In [69]: while b != []:

    ...:     b_s.add(b.pop())

    ...:

In [70]: answer = set.intersection(a_s, b_s)

In [71]: answer

Out[71]: {2, 3, 4}

时间复杂度

1. 遍历堆栈1并添加到集合： O(n)

2. 遍历堆栈2并添加到set：中O(n)。或者只是通过查询您在上面所做的集合并添加到答案集合中来快速计算交点，这将为您节省一些时间

3. 对于set1中的每个项目，请在set 2中执行恒定时间查找。 O(n)

4. 可能打印答案： O(n)

5. 全面的： O(n) * 3(or 4) ~= O(n)

我的理由是为什么没有多线程就无法更快地运行。排序是您不必查看元素的事情，但是除非您可以按真实的线性时间进行排序，否则它将花费更多的时间O(n)。如果不分析另一个堆栈中每个堆栈中的每个元素，就无法计算交集。您只能优化从一个O(n)操作到另一个O(constant)操作的上下文分析。

另外，因为您说过您使用的是专用列表堆栈，所以我不认为偷看未弹出的元素是允许的

Answer 2

在您的情况下，我不太了解如何使用二进制搜索。

一种可能的方法是将列表A和列表B分成两半，以便您有4个列表。由于没有竞争条件，因此您可以使用多线程来更快地运行线性比较。

这是有关如何使用多线程的教程：