我在职业杯上读了这个问题，但除了'SkipList'之外没有找到任何好的答案。我在维基百科上找到的SkipList的描述很有趣，然而，我不理解一些术语，如"几何/二项分布"……我读了它是什么，深入研究了概率论。我只是想实现一种使某些搜索更快的方法。我是这样做的:1. 创建索引。-我写了一个函数来创建1000个节点。然后，我创建了一个链表类型的数组，循环遍历1000个节点，并选择每23个元素(我脑海中出现的随机数)并添加到数组中，我称之为"索引"。
SLL index = new SLL[50]
private static void createIndex(SLL[] index, SLL head){
int count=0;
SLL temp = head;
while(temp!=null)
{
count++;
temp = temp.next;
if((count==23){
index[i] = temp;
i++;
count=0;
}
}
}
最后是'find'函数。在这个函数中，我首先以输入元素769为例。我遍历'index'数组，发现index[I]>769。因此，现在我将head = index[I -1]和tail = index[I]传递给'find'函数。然后，它将在23个元素的短范围内搜索769。因此，我计算出总共需要43次跳转(包括数组跳转和node=node)。下一次跳跃)来找到我想要的元素，否则需要进行769次跳跃。
请注意:我认为创建索引数组的代码不是搜索的一部分，因此我不添加它的时间复杂度(这是可怕的)与'find'函数的时间复杂度。我认为索引的创建应该在创建列表之后作为一个单独的函数来完成，或者及时完成。就像一个网页在谷歌搜索中出现需要时间一样。此外，这个问题在微软的面试中被问到，我想知道我提供的解决方案是否有任何好处，或者我提供这样的解决方案会不会看起来像个傻瓜。解决方案是用Java编写的。等待您的反馈
很难弄清楚你在这里要解决的是什么问题，或者你的解决方案应该如何工作。(提示:完整的工作代码对两者都有帮助!)
然而，我们可以这样说:
-
你不能搜索列表数据结构(例如，在列表中找到
i)比O(N)更好，除非在其上放置了某种排序。例如，对元素进行排序 -
如果列表的元素被排序并且您的列表是可索引的(即获得位置
i的元素是O(1))，那么您可以使用二进制搜索并找到O(logN)中的元素。 -
链表中
i位置的元素不能比O(N)位置的元素更好
如果你添加辅助数据(索引，等等)，你可能会在某些操作中获得更好的性能…以更多的存储空间为代价，并使某些其他操作更加昂贵。但是，您不再拥有列表/链表。整个数据结构是"别的东西"