查找多个跳过列表的交叉点

Question

这是用于查找两个跳过列表的交点的算法：

（查找两个跳过列表的交叉点 - 对斯坦福大学的版权）

我们可以看到，与一次移动一步相比，“跳过跳跃”在效率方面受益匪浅。

但是在这里我很好奇，如果将这种情况扩展到多个跳过列表，说100个列表怎么办？目前，我只考虑分裂和征服，其中多个跳过列表按2分组，并顺序得出其相交，然后合并解决方案，这听起来很耗时且效率低下。

确定多个跳过列表的相交以及花费最少的时间的更好方法是什么？

Answer 1

初始化一个指针，直达每个跳过列表的开头。

我们将维护两件事：

• 当前的最大值指向
• （值，指针）对的最小值。

在每个步骤：

• 检查所有指针是否具有相同的值，通过将Min-Heap的顶部与最大值进行比较。
  • 如果这两个是相同的：
    • 所有当前值必须相同（因为min == max），因此该值在交点中。
    • 将该值添加到输出中。
    • 弹出您的小矿床，将其指针推进，直到达到更大的价值，然后推动新价值。将最大最大更新为新值。
  • 其他：
    • 弹出您的小矿山，推进其指向最大值的指针，根据需要跳过。
    • 如果其新值超过最大值，请更新最大值。
    • 将新价值推向您的遥远。

当任何列表耗尽时停止（您需要推进指针，但不能推进。）

这是经典编程面试问题“合并K分类列表”的略有变化 - 这里的算法非常相似。我建议看看这个答案中的任何东西尚不清楚。