Java中快速算法反转数组

Question

我编写了代码来反转具有时间复杂度的数组:O(n).

有更快的方法吗？

我的代码:

 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);   
    }

Answer 1

字面上颠倒内存中的元素不能比O(n)更快地完成.但是,您可以创建一个包装类来反转索引数组.因此,实际上您不会反转数组,而只能向后访问元素.

你拥有的代码是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;
    }
}