有没有最快的方法来反转由两种类型的元素组成的数组中元素的范围？

Question

我有一个数组，假设：
2, 3, 3, 2, 3, 3, 3, 2

（数组由两个唯一的整数组成，重复）

给定L和R（表示数组内的范围）。
是否有任何最快的方法来反转 L 到 R 范围内的数组元素？
目前，我在 O(n) 中进行。

对于上面的示例，如果 L=2 且 R=5，则新数组将为，
2、3, 2, 3, 3、3、3、2

我经历了这个解决方案： Reversing an array Query

但是想知道除了decorated splay trees之外还有没有其他方法？

Answer 1

我认为没有更快的方法（由于 swap 操作），但您可以使用其他数据结构。

我猜这里的想法是使用一种带有操作 go through 的双链表，它将通过访问

来传递列表

next sibling 如果 next 不是 before
before sibling 如果 next 是 before

在类似这样的伪代码中：

class Node
{
    Node before, next;
}

void goThrough(Node root, Node currentNode)
{
     //some actions here

     if( root.next != null || root.next != currentNode )
     {
         goThrough( root.next );
     }

     if( root.before != null )
     {
         goThrough( root.before );
     }
}

那么反转范围将只是改变范围开始和结束处的 next/before 字段 - 这实际上使得 O(1)

有没有最快的方法来反转由两种类型的元素组成的数组中元素的范围？

Is there any fastest approach to reverse the range of elements in an array consisting of two types of elements?

arrays

algorithm

optimization

reverse

range