在 O(m + n) 中合并跳表
Merge Skip Lists in O(m + n)
我被要求编写一个实现，以 O (m + n) 时间复杂度合并 n 个元素的跳跃列表 A 和 m 个元素的跳跃列表 B。我不需要代码，只是一个基本的解释，我可以如何实现它。
我想遍历 A，遍历 B 并比较值，然后将其合并到一个新的跳过列表 C 中，但这似乎是二次的。还是我遗漏了什么？
根据定义，跳过列表以某种方式排序（例如“按数字递增顺序”或“按姓氏字母顺序”或诸如此类），使用其元素的总顺序 space.
对于您的问题，您肯定应该假设 A 和 B 的排序方式相同，并且您知道这种方式是什么，这样您就可以判断 A 中的给定元素是否小于、大于或等于 B[= 中的给定元素33=].
如果是这样，那么您可以编写一个循环，在每次迭代中比较每个列表的“下一个”元素。如果来自 A 的“下一个”元素——称之为 ai——小于“下一个” " 来自 B 的元素，那么你知道 ai 没有出现在 B 并且小于您尚未检查的任何元素，因此您可以将 ai 附加到结果列表并继续 A 的下一个元素。反之亦然。 （当然，如果两个元素相等，那么您只需追加一个并继续每个列表的下一个元素。）
（这不是特定于跳过列表；您可以使用相同的方法合并 any 两个排序列表，而不管用于实现这些列表的特定数据结构如何，只要它们以相同的方式排序并且您知道那是什么。）
我被要求编写一个实现，以 O (m + n) 时间复杂度合并 n 个元素的跳跃列表 A 和 m 个元素的跳跃列表 B。我不需要代码，只是一个基本的解释，我可以如何实现它。
我想遍历 A，遍历 B 并比较值，然后将其合并到一个新的跳过列表 C 中，但这似乎是二次的。还是我遗漏了什么？
根据定义，跳过列表以某种方式排序（例如“按数字递增顺序”或“按姓氏字母顺序”或诸如此类），使用其元素的总顺序 space.
对于您的问题，您肯定应该假设 A 和 B 的排序方式相同，并且您知道这种方式是什么，这样您就可以判断 A 中的给定元素是否小于、大于或等于 B[= 中的给定元素33=].
如果是这样，那么您可以编写一个循环，在每次迭代中比较每个列表的“下一个”元素。如果来自 A 的“下一个”元素——称之为 ai——小于“下一个” " 来自 B 的元素，那么你知道 ai 没有出现在 B 并且小于您尚未检查的任何元素，因此您可以将 ai 附加到结果列表并继续 A 的下一个元素。反之亦然。 （当然，如果两个元素相等，那么您只需追加一个并继续每个列表的下一个元素。）
（这不是特定于跳过列表；您可以使用相同的方法合并 any 两个排序列表，而不管用于实现这些列表的特定数据结构如何，只要它们以相同的方式排序并且您知道那是什么。）