Java 中反转数组的快速算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/21023348/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fast Algorithm in Java to Reverse an Array
提问by Nihal Harish
I have written code to reverse an array that has Time Complexity: O(n).
我编写了代码来反转时间复杂度为 O(n) 的数组。
Is there a faster method?
有没有更快的方法？
My code:
我的代码：
void reverseArray(int arr[], int start, int end){
int temp;
if(start >= end)
return;
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
reverseArray(arr, start+1, end-1);
}
采纳答案by Martijn Courteaux
Literally reversing the elements in memory can't be done any faster than O(n). However, you could make a wrapper class that indexes the array reversed. So, in fact you don't reverse the array, but only access the elements backwards.
从字面上看，反转内存中的元素不能比 O(n) 快。但是，您可以创建一个反向索引数组的包装类。因此，实际上您不会反转数组，而只会向后访问元素。
The code you have is O(n), but terrible because of the recursion. Make it flat and you will experience some benefit.
您拥有的代码是 O(n)，但由于递归而很糟糕。把它弄平，你会体验到一些好处。
public static void reverseArray(int arr[], int start, int end)
{
int len = end - start;
if(len <= 0) return;
int len2 = len >> 1;
int temp;
for (int i = 0; i < len2; ++i)
{
temp = arr[start + i];
arr[start + i] = arr[end - i - 1];
arr[end - i - 1] = temp;
}
}
回答by Tim B
You are using recursion which is not as fast as a loop. You are still O(n) but with faster time to use a loop. Something like:
您使用的递归不如循环快。您仍然是 O(n) 但使用循环的时间更快。就像是：
static void reverseArray(int arr[]){
for (int start=0,end=arr.length-1;start<=end;start++,end--) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
}
For something like this you will be better off using methods provided in the Java libraries to do it though.
对于这样的事情，您最好使用 Java 库中提供的方法来完成它。
回答by nmargaritis
If you use static arrays, since you will need to access every element once in order to reverse it, there is no smaller complexity than n.
如果您使用静态数组，因为您需要访问每个元素一次才能反转它，所以没有比 n 更小的复杂性。
However, if you use a double linked list, then by definiton you have access to the elements in both directions. From head to tail and from tail to head, because there are double pointers in the Node class used. Therefore, reverse is not even needed, but rather you iterate from tail to head when needed.
但是，如果您使用双链表，那么根据定义，您可以在两个方向上访问元素。从头到尾和从尾到头，因为使用的Node类中有双指针。因此，甚至不需要 reverse，而是在需要时从尾部迭代到头部。
回答by tomwesolowski
You could use some intermediary function:
您可以使用一些中间函数：
int rev(int i) {
return arr.length - i - 1;
}
//...
arr[rev(i)] = 5; // reverse reference
回答by mcsilvio
Recursion vs Iteration. Function calls (recursion) cost cycles. Thus, for this solution, I would go with an iterative approach. Other things to note are: even/odd sized arrays, empty arrays, arrays with only 1 item. An untested solution is:
递归与迭代。函数调用（递归）成本周期。因此，对于这个解决方案，我会采用迭代方法。其他需要注意的是：偶数/奇数大小的数组、空数组、只有 1 个项目的数组。一个未经测试的解决方案是：
void reverseArray(int arr[]){
//check input
if(arr.length <= 1){
return;
}
int arrLength = arr.length;
int swpIndex;
for (int i = 0; i < arrLength / 2 - 1; i++){
swpIndex = arrLength - i - 1;
swp = arr[i];
arr[i] = arr[swpIndex];
arr[swpIndex] = swp;
}
}
This stores a few values so that it really avoids repitition (i.e. extra cycles). It also checks for arrays that don't need reversing.
这会存储一些值，以便真正避免重复（即额外的周期）。它还检查不需要反转的数组。
