java - 编写一个名为的递归方法，该方法接受一个整数数组并以相反的排序顺序返回该数组

Question

几天后我有一场编程考试，所以我正在做一些练习只是为了练习。然而，我一直被这个问题困扰，我开始怀疑是否可以做到这一点。 编写一个名为 arrayReverse 的递归方法，它接受一个整数数组并以相反的排序顺序返回所述数组。因此，一个例子是:

input: [1,2,3]    
output:[3,2,1]

我没能解决这个问题。我的直觉是取出数组的最后一个元素，将其放在开头，即:index[0]，然后递归调用数组的其余部分，然后取出新的最后一个元素并将其放在索引[1]上。不幸的是，实现比我想象的要难，但我(为了尝试)以接受 2 个数组的方式编辑了问题，这是我的代码:

import java.util.Arrays;

class Test {

  int[] arrayReverse(int[] m, int[] mReverse) {
    if (m.length == 1) {
        mReverse[mReverse.length - 1] = m[0];
        return mReverse;
    } else {
        int lastNum = m[m.length - 1];
        mReverse[mReverse.length - m.length] = lastNum;
        int[] arrayMinusOne = cropArray(m);
        return arrayReverse(arrayMinusOne, mReverse);
    }
}

int[] cropArray(int[] m) {
    int[] mCropped = new int[m.length - 1];
    for (int i = 0; i < m.length - 1; i++) {
        mCropped[i] = m[i];
    }
    return mCropped;
}

}
  void demo() {

    int[] helpTest4 = new int[]{1, 2, 3};
    int[] emptyArray = new int[helpTest4.length];

    int[] test4 = arrayReverse(helpTest4, emptyArray);
    System.out.println(Arrays.toString(test4));


}

public static void main(String[] args) {
    new Test().demo();
}
}

它工作得很好，但我对结果不满意，因为两个原因:

1. 我无法完全递归地完成它。我在cropArray 中使用了for 循环。
2. 我无法在一个数组上做到这一点。

如何做到这一点？

Answer 1

选项1:在递归函数中仅使用一个参数(数组)

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

public class MyClass {
     public static void main(String[] args) {

        int[] arr = {1,2,3,4,5};
        int[] reversed = reverseArray(arr);
        System.out.println(Arrays.toString(reversed));
    }

    public static int[] reverseArray(int[] arr)
    {
        if (arr.length == 0)
            return arr;

        // remove first element   
        int first = arr[0];
        int[] list = Arrays.copyOfRange(arr, 1, arr.length);

        //Calling Function Recursively get reversed array
        int[] returnArr = reverseArray(list);

        //Add original first to the last of the arrayToReturn
        returnArr = Arrays.copyOf(returnArr, returnArr.length + 1);
        returnArr[returnArr.length - 1] = first;

        return  returnArr;
    }
}

选项2:

void reverseArray(int[] x){
   reverse(x, 0, x.length -1);
}

void reverse(int[] x, int i, int j){
    if(i<j){//Swap ith with jth element where i and j are equidistant from ends
       int tmp = x[i];
       x[i] = x[j];
       x[j] = tmp;
       reverse(x, ++i, --j);//Recursive
    }   
}

测试:

int[] s = new int[]{1,2,3,4,5};
reverseArray(s);
System.out.println(Arrays.toString(s));//"5,4,3,2,1"

递归，O(n)，不需要临时数组。