在少于O(n)时间内反转一个数组的子数组

Question

如何在少于O(n)时间内反转数组(或任何其他数据结构，如链表(非双链表))的子数组(例如从第i个索引到第j个索引)?O(n)的时间消耗是微不足道的。(我想在数组上做很多次这样的反转，比如从一开始反转n次(每次，向前移动一个索引，然后再反转)所以应该有一种方法，它的平摊分析会给我们一个小于O(n)的时间消耗，知道吗?
提前感谢:)

Answer 1

我认为你想用错误的方法来解决这个问题。我猜你是想从整体上改进算法，而不是O(n)逆运算。这是不可能的。如果你要考虑n个元素中的每一个，你总是有O(n)

就像我说的，你能做的就是改进O(n^2)算法。你可以用O(n)来解它假设我们有这样一个列表:

a b c d e

然后使用你的算法修改这个列表:

e d c b a
e a b c d

等等…最后你得到这个:

e a d b c

如果你有两个指针来自数组的两端，并且在指针之间交替(自增/自减/获取值)，你可以得到这个列表。整个过程是O(n)

这个算法的更详细的解释:

使用前面的列表，我们希望元素的顺序如下:

a b c d e
2 4 5 3 1

创建了两个指针。一个指向列表的开头，另一个指向列表的末尾:

a b c d e
^       ^
p1      p2

则算法工作如下:

1. Take the value of p2
2. Take the value of p1
3. Move the pointer p2 one index back
4. Move the pointer p1 one index further
5. If they point to the same location, take the value of p1 and stop.
   or if p1 has passed p2 then stop.
   or else go to 1.

Answer 2

对于给定的数组，您可以在O(n)时间内完成。这里l表示起始索引，r表示结束索引。所以我们需要将子数组从r反转到l

public void reverse(int[] arr, int l, int r)
  {
      int d = (r-l+1)/2;
      for(int i=0;i<d;i++)
      {
         int t = arr[l+i];
         arr[l+i] = arr[r-i];
         arr[r-i] = t;
      }
    // print array here 
  }

Answer 3

如上文所述，O(n)是最小值。你必须移动n个项目到它们的新位置。

既然你提到了链表，这里有一个O(n)的解决方案。

如果您移动所有节点并反转它们的方向，然后将其末端与列表的其余部分绑定，则子列表将被反转。所以:

1->2->3->4->5->6->7->8->9

倒转4到7将改变:

4->5->6->7

为:

4<-5<-6<-7

让3指向7，让4指向8。

为了保持一致性，有些复制了duedlor的格式:

 1. Move to the item before the first item to reorder(n steps)
 2. remember it as a (1 step)
 3. Move to the next item (1 step)
 4. Remember it as b (1 step)
while not at the last item to reorder: (m times)
 5. Remember current item as c (1 step)
 6. Go to next item (1 step)
 7. Let the next item point to the previous item (1 step)
having reached the last item to reorder:
 8. let item a point to item c (1 step)
if there is a next item:
 9. move to next item (1 step)
 10. let item b point to current item (1 step)

这是O (n + 1 + 1 + 1 + m *(1 + 1 + 1 + 1 + 1 + 1)。除去大O中不允许的所有数字，就是O(n+m)，可以称为O(n+n)，也可以称为O(2n)

等于0 (n)