倒车子数组的数组，在不到O（n）的时间 [英] Reversing a sub-array of an array , in less than O(n) time

问题描述

我们如何能扭转一个子（比方说从第i个指标第j个指标）的阵列（或任何其他数据结构，如链表（不是双））中，在小于O（n）的时间？在O（n）时间消耗是微不足道的。（我想这样做回归的数组很多次，好像从一开始每次启动和倒车它n次（，向前迈进的一个索引，然后再倒车吧），所以应该有一种方法，它的平摊分析将会给我们一个时间耗小于O（N），任何想法？
在此先感谢：）

how can we reverse a subarray ( say from i-th index to j-th index ) of an array ( or any other data structure , like linked-list ( not doubly )), in less than O(n) time ? the O(n) time consumption is trivial.( I want to do this reversion many times on the array , like starting from the beginning and reversing it for n times (each time , going forward for one index and then reversing it again), so there should be a way ,which its amortized analysis would give us a time consumption less than O(n) , any idea ?
thanks In advance :)

推荐答案

我觉得要解决这个问题有一个错误的做法。我猜你想提高算法作为一个整体，而不是O（n）的反转的东西。因为这是不可能的。你总是为O（n），如果你要考虑每个n个元素。

I think you want to solve this with a wrong approach. I guess you want to improve the algorithm as a whole, and not the O(n) reversing stuff. Because that's not possible. You always have O(n) if you have to consider each of the n elements.

就像我说的，你可以做的是提高为O（n ^ 2）算法。您可以解决在为O（n）： 比方说，我们有这样的名单：

As I said, what you can do is improve the O(n^2) algorithm. You can solve that in O(n): Let's say we have this list:

a b c d e

您然后使用你的算法修改此列表：

You then modify this list using your algorithm:

e d c b a
e a b c d

等..到底你有这样的：

and so on.. in the end you have this:

e a d b c

您可以获取此列表，如果你有两个指针的指针（递增/递减/获取值）之间的阵列和备用的两端到来。它给你O（n）的整个过程。

You can get this list if you have two pointers coming from both ends of the array and alternate between the pointers (increment/decrement/get value). Which gives you O(n) for the whole procedure.

该算法的更详细的解释：

More detailed explanation of this algorithm:

使用previous名单，我们希望在后续顺序的元素：

Using the previous list, we want the elements in the follow order:

a b c d e
2 4 5 3 1

所以，你创建了两个三分球。一个指向在列表的开头，另外一个在末尾

a b c d e
^       ^
p1      p2

然后，算法的工作方式如下：

Then the algorithms works as follows:

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.

这篇关于倒车子数组的数组，在不到O（n）的时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！