所以我需要从头开始移动第 n 个元素并将其移动到前面（并将 0、..、n-1 个项目向右移动）。什么是最好的数据结构，我应该怎么做？
我已经在考虑跳过列表，但不知道如何通过索引获取 O(log n) 进行访问。有没有更好的东西（树或其他东西）我应该使用？
提前致谢..
语言：C++
免责声明：是的，这是家庭作业。
问问题
2157 次
5 回答
6
You can use any balanced binary tree (e.g. a red-black tree) where in each node you cache the number of items stored in that subtree. The items themselves can be stored in the leaves. For indexed lookup, you compare the index with the size of the left subtree. If it's smaller, it's there. Otherwise it's in the right side, so subtract the size of the left subtree from the index to get the index relative to the right subtree. Then recurse. Since the tree is balanced, this gives you O(log n).
For the other operations you can use the existing algorithms for red-black trees. You just need some small modifications to keep track of the size. For example, to move an item to the front, you first find it using the algorithm described above, then delete it and reinsert it at the front. Each of these steps is O(log n), so the total runtime is also O(log n).
于 2013-05-26T14:51:37.327 回答
2
这些问题总是围绕一个基本原则，你可以把它想象成计算机科学的“没有免费的午餐”：时间和空间之间的权衡。
如果你想非常快地做某事，你需要消耗更多的空间，反之亦然。
例如，数组是小空间的最佳选择，但当你需要移动某些东西时，它是可怕的。Hashtable 是快速访问的最佳案例，但会消耗过多的浪费空间。
所以你必须决定哪个更重要，空间经济还是时间经济。
在这种情况下，如果您正在寻找 O(log n) 的索引 lokup，您可以使用跳过列表或索引跳过列表。这些数据结构提供了链表的好处（容易将第 n 个元素移到前面，只需更改两个指针）和数组的好处（索引查找），但以空间为代价（更多的指针存储到“跳过”列表）。
于 2013-05-26T14:44:05.933 回答
0
我想你可以选择 LinkedHashMap 类型的 DS。在 java 中有一个 LinkedHashMap的内置实现。因此，在第一个位置移动最后一个对象涉及删除最后一个对象，然后将其添加到同一个 DS。搜索可以再次在 O(1) 时间内完成。在其他语言中，使用 LinkedList 作为主要 DS 并由 HashMap DS 以及它来实现也不是一件难事。
于 2013-05-26T14:42:21.737 回答
0
我不知道空间复杂性，但你可以使用指针数组和链接列表在 O(1) 时间内做同样的事情（你希望数据在前面，就像你在数组的情况下所说的那样）。制作一个数字的链表和一个相同大小的数组，以相同的顺序存储链表节点的地址。对于任何第 n 个值，从数组中选择第 n 个节点和第一个节点的地址并替换这些节点的数字......
于 2013-05-26T14:46:16.923 回答
0
也许双向链表可以:) 当您使用双向链表时：
索引需要 O(n)，因为我们需要遍历从开始到所需索引的所有元素。
删除操作很简单，只需要 O(1)。
在前面移动所需元素的操作也需要 O(1)。
总的来说，你会得到〜O（n）次操作......
于 2013-05-26T14:49:57.313 回答