algorithm - 具有大量操作的自组织数字序列 - 最佳数据结构

Question

我需要帮助来为我的练习选择正确的数据结构。

对于输入，我已经给出了应该执行的操作数(t)，然后是用空格分隔的自然数索引序列。例如:

3 1 2 3

这意味着将在序列 {1,2,3} 上执行 3 个操作。

还定义了一个指针，表示当前位置。我应该对该序列执行的操作是:

• R -> 删除索引 PTR+1 上的元素 c 并向前移动 PTR < em>c 次

• X -> 在索引 PTR 上的元素 c 之后插入(所以插入在 PTR+ 1)，元素的值为 c-1，当然会将 PTR 向前移动 c 次。

  <

我的工作是在执行 R 和 X t 次操作后找到结束序列，这样如果它的元素是偶数 然后执行 R，否则执行 X。在开始时 PTR 显示第一个元素(如果存在)并且它应该全部在循环中。

对于帖子开头的给定示例，输出应该是:

0 0 3 1

我知道这听起来可能令人困惑，所以让我逐步向您展示这应该如何工作。

t = 1

Starting sequence: 1 2 3

Actual position: PTR -> 1

Operation: X, c=1

Ending sequence: 1 0 2 3

Ending position: PTR -> 0

t = 2

Starting sequence: 1 0 2 3

Actual position: PTR -> 0

Operation: R, c=2

Ending sequence: 1 0 3

Ending position: PTR -> 1

t = 3

Starting sequence: 1 0 3

Actual position: PTR -> 1

Operation: X, c=1

Ending sequence: 1 0 0 3

Ending position: PTR -> 0

解决方案是 PTR 中正确方向的序列。所以输出应该是:0 0 3 1

关于限制:

• C序列的起始长度可达10^7

• t 操作数高达 10^7

• 将 PTR 向右移动最多 10^9 次

我已经创建了我的算法，它基于循环链表。有效，但对于某些测试来说太慢了。如果有人可以帮助我找到最佳数据结构，我将不胜感激。

我的老师也提示我应该使用二进制列表，但老实说，我在互联网上没有找到任何关于这种结构的信息!也许还有人知道这件事并告诉我在哪里可以搜索有关它的信息？如果有任何帮助，我将不胜感激。

Answer 1

使用 circular doubly linked list .它有 O(1) 插入和删除。 (也许这就是您的导师所说的“二进制列表”的意思。)

有趣的事实:您可以使用 XOR trick 减少双向链表的内存使用率与 code here .由于更好的缓存行为，较低的内存利用率将意味着大型列表的速度更快。还有一个 SO Q&A在 XOR 链表上，列举了它的一些缺点。