0

我在职业杯上阅读了这个问题，但除了“SkipList”之外没有找到任何好的答案。我在 wikipedia 上找到的 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;
        }
    }       
}

现在终于是“查找”功能了。在该函数中，我首先以输入元素 769 为例。我遍历'index'数组并找到index[i]>769。因此，现在我将 head = index[i-1] 和 tail = index[i] 传递给“find”函数。然后它将在 23 个元素的短范围内搜索 769。因此，我计算出总共需要 43 次跳转（包括数组跳转和 node=node.next 跳转）才能找到我想要的元素，否则会有跳了 769 次。

请注意：我认为创建索引数组的代码不是搜索的一部分，因此我不会将其时间复杂度（这很糟糕）与“查找”函数的时间复杂度相加。我假设索引的创建应该在创建列表后作为单独的函数完成，或者及时进行。就像网页在谷歌搜索中出现需要时间一样。另外，这个问题是在微软的一次采访中被问到的，我想知道我提供的解决方案是否有用，或者我看起来像个傻瓜，提供了这样的解决方案。解决方案是用 Java 编写的。等待您的反馈意见。

4

1 回答 1

1

很难弄清楚您要在这里解决什么问题，或者您的解决方案应该如何工作。（提示：完整的工作代码对两者都有帮助！）

但是，我们可以说一些一般的事情：

  • 您无法i更好地搜索列表数据结构（例如在列表中查找），O(N)除非已对其进行了某种排序。例如，对元素进行排序。

  • 如果列表的元素已排序并且您的列表是可索引的（即获取位置i为的元素O(1)），那么您可以使用二进制搜索并在O(logN).

  • 您无法i更好地获取链表位置处的元素O(N)。

如果您添加辅助数据（索引等），您可能会为某些操作获得更好的性能......但会牺牲更多的存储空间，并使某些其他操作更加昂贵。但是，您不再拥有列表/链表。整个数据结构是“别的东西”。

于 2015-11-01T02:04:28.567 回答