所以我需要从头开始移动第n个元素并将其移动到前面(并向右移动0,..,n-1项).什么是最好的数据结构使用,我应该怎么做？
我已经在考虑跳过列表,但不知道如何通过索引获取O(log n)以进行访问.我应该使用更好的东西(树木或东西)吗？
提前致谢..
语言:C++
免责声明:是的,这是作业.
您可以使用任何平衡二叉树(例如红黑树),在每个节点中缓存存储在该子树中的项目数.物品本身可以存储在树叶中.对于索引查找,可以将索引与左子树的大小进行比较.如果它更小,它就在那里.否则它在右侧,因此从索引中减去左子树的大小以获得相对于右子树的索引.然后递归.由于树是平衡的,这给你O(log n).
对于其他操作,您可以将现有算法用于红黑树.您只需要进行一些小修改即可跟踪大小.例如,要将项目移到前面,首先使用上述算法找到它,然后将其删除并重新插入前面.这些步骤中的每一步都是O(log n),因此总运行时间也是O(log n).