algorithm - 在 O(m + n) 中合并跳过列表

Question

我被要求编写一个实现，以 O (m + n) 时间复杂度将包含 n 个元素的跳过列表 A 与包含 m 个元素的跳过列表 B 合并。我不需要代码，只是一个基本的解释我如何实现这一点。

我想过遍历 A，遍历 B 并比较值，然后将其合并到新的跳过列表 C 中，但这似乎是二次的。还是我错过了什么？

标签： algorithmdata-structuresmergeskip-lists

Answer 1

根据定义，跳过列表以某种方式排序（例如“按数字递增顺序”或“按姓氏字母顺序”或诸如此类），使用其元素空间的某种总顺序。

对于您的问题，您当然应该假设A和B的排序方式相同，并且您知道这种方式是什么，以便您可以判断A中的给定元素是小于、大于还是与B中的给定元素相同。

如果是这样，那么您可以编写一个循环，在每次迭代中比较每个列表的“下一个”元素。如果A中的“下一个”元素（称为a _i）小于B中的“下一个”元素，那么您知道a _i没有出现在B中并且小于您尚未检查的任何元素，因此您可以将a _i附加到您的结果列表并继续处理 A 的下一个元素。而且，反之亦然。（当然，如果两个元素相等，那么您只需附加一个并继续到每个列表的下一个元素。）

（这对跳过列表不是很具体；您可以使用相同的方法来合并任何两个排序列表，而不管用于实现这些列表的特定数据结构，只要它们以相同的方式排序并且您知道什么就是这样。）