python - 找到 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

在你的例子中，我不太明白你如何使用二进制搜索。

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

这是关于 how to use multithreading: 的教程