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)的时间内反转一个数组(或任何其他数据结构,如链表(不是双重))的子数组(比如从第i个索引到第j个索引)? O(n)时间消耗是微不足道的。(我想在数组上多次进行这种反转,比如从头开始并将其反转n次(每次,一个索引然后再反转),所以应该有一种方法,它的摊销分析会给我们一个小于O(n)的时间消耗,任何想法?谢谢提前:)
3 个解决方案
#1
4
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)反转的东西。因为那是不可能的。如果你必须考虑n个元素中的每一个,你总是有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:
正如我所说,你可以做的是改进O(n ^ 2)算法。你可以在O(n)中解决这个问题:假设我们有这个列表:
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
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.
如果有两个指针来自数组的两端并在指针之间交替(增量/减量/获取值),则可以获取此列表。这给了你整个程序的O(n)。
More detailed explanation of this algorithm:
该算法的更详细解释:
Using the previous list, we want the elements in the follow order:
使用上一个列表,我们希望以下顺序中的元素:
a b c d e
2 4 5 3 1
So you create two pointers. One pointing at the beginning of the list, the other one at the end:
所以你创建了两个指针。一个指向列表的开头,另一个指向最后:
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.
#2
0
As duedl0r mentioned, O(n) is your minimum. you will have to move n items to their new position.
正如duedl0r所提到的,O(n)是你的最低要求。你必须将n个项目移动到新的位置。
Since you mentioned a linked list, here's an O(n) solution for that.
既然你提到了一个链表,这里有一个O(n)解决方案。
If you move through all nodes and reverse their direction, then tie the ends to the rest of the list, the sublist is reversed. So:
如果您移动所有节点并反转它们的方向,然后将末端绑定到列表的其余部分,则子列表会反转。所以:
1->2->3->4->5->6->7->8->9
reversing 4 through 7 would change:
倒转4到7会改变:
4->5->6->7
into:
4<-5<-6<-7
Then just let 3 point to 7 and let 4 point to 8.
然后让3指向7并让4指向8。
Somewhat copying duedl0r's format for consistency:
有点复制duedl0r的格式以保持一致性:
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)
That's O(n+1+1+1+m*(1+1+1)+1+1+1). Without all the numbers that aren't allowed in Big O, that's O(n+m), which may be called O(n+n), which may be called O(2n).
那是O(n + 1 + 1 + 1 + m *(1 + 1 + 1)+ 1 + 1 + 1)。如果没有Big O中不允许的所有数字,那就是O(n + m),可以称为O(n + n),可以称为O(2n)。
And that's O(n).
这就是O(n)。
#3
0
You can do it O(n) time for given array. Here l represents starting index and r represents end. So we need to reverse subarray from r to l.
对于给定的数组,您可以在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
}
#1
4
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)反转的东西。因为那是不可能的。如果你必须考虑n个元素中的每一个,你总是有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:
正如我所说,你可以做的是改进O(n ^ 2)算法。你可以在O(n)中解决这个问题:假设我们有这个列表:
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
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.
如果有两个指针来自数组的两端并在指针之间交替(增量/减量/获取值),则可以获取此列表。这给了你整个程序的O(n)。
More detailed explanation of this algorithm:
该算法的更详细解释:
Using the previous list, we want the elements in the follow order:
使用上一个列表,我们希望以下顺序中的元素:
a b c d e
2 4 5 3 1
So you create two pointers. One pointing at the beginning of the list, the other one at the end:
所以你创建了两个指针。一个指向列表的开头,另一个指向最后:
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.
#2
0
As duedl0r mentioned, O(n) is your minimum. you will have to move n items to their new position.
正如duedl0r所提到的,O(n)是你的最低要求。你必须将n个项目移动到新的位置。
Since you mentioned a linked list, here's an O(n) solution for that.
既然你提到了一个链表,这里有一个O(n)解决方案。
If you move through all nodes and reverse their direction, then tie the ends to the rest of the list, the sublist is reversed. So:
如果您移动所有节点并反转它们的方向,然后将末端绑定到列表的其余部分,则子列表会反转。所以:
1->2->3->4->5->6->7->8->9
reversing 4 through 7 would change:
倒转4到7会改变:
4->5->6->7
into:
4<-5<-6<-7
Then just let 3 point to 7 and let 4 point to 8.
然后让3指向7并让4指向8。
Somewhat copying duedl0r's format for consistency:
有点复制duedl0r的格式以保持一致性:
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)
That's O(n+1+1+1+m*(1+1+1)+1+1+1). Without all the numbers that aren't allowed in Big O, that's O(n+m), which may be called O(n+n), which may be called O(2n).
那是O(n + 1 + 1 + 1 + m *(1 + 1 + 1)+ 1 + 1 + 1)。如果没有Big O中不允许的所有数字,那就是O(n + m),可以称为O(n + n),可以称为O(2n)。
And that's O(n).
这就是O(n)。
#3
0
You can do it O(n) time for given array. Here l represents starting index and r represents end. So we need to reverse subarray from r to l.
对于给定的数组,您可以在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
}