时间戳

首页 > 解决方案 > 链表，在log(k)中实现peekAt(k)方法

data-structures - 链表，在log(k)中实现peekAt(k)方法

问题描述

我被要求设计一个数据结构，它就像一个堆栈，大小不受限制，它将支持以下方法，并具有给定的运行时限制。

push(s) - 将 s 推送到数据结构 - O(1) pop() - 删除并返回最后插入的元素 O(1) middle() - 按插入顺序返回索引为 n/2 的元素（不删除）其中 n 是数据结构中元素的当前数量。- O(1) peekAt(k) - 按插入顺序返回第 k 个元素（栈底为 k=1） - O(log(k))

这 3 种方法将使用链表，但我应该如何实现 peekAt(k) 方法。

谢谢你。

标签： data-structureslinked-listtime-complexity

解决方案

您正在寻找的是Skip List的变体，它按插入顺序排序。

为了支持O(logk)而不是 ,您实际需要的唯一修改是O(logn)在开始搜索之前从下到上，例如：

// Assume head points to the first element in the lower tier list.
current = head
while (current->next->index < k) current = current->up

此时，您要查找的元素介于current和之间current->next。您可以使用常规的跳过列表搜索值来查找它k，从current顶层而不是顶层开始。

请注意，查找current是在 中完成的O(logk)，因为您基本上是反复检查：

1 < k ?
2 < k ?
4 < k ?
8 < k ?
...
2^ceil(logk) < k ?

也就是说，O(log(k)) 检查。

推荐阅读