java - 如何更高效地编写递归左移数组算法

Question

我今天在 HackerRank 上完成了一些练习题，还有一个问题要求我编写一个算法，将数组中的所有元素左移 n 次(即 rotLeft({1, 2, 3, 4, 5} , 1) 返回 {2, 3, 4, 5, 1}), 由于我的算法效率低下，我遇到了经典的超时错误。这不是我第一次因为在线编码系统编写低效的算法而受到批评。真的，我有两个问题:1)如何专门重写我的左移算法以提高时间效率？ 2) 一般来说，我该如何提高运行效率低下的算法的性能？

public static final int NULL = -2147483648;

static int[] rotLeft(int[] a, int d) {
    return rotLeftRec(a, d, 0);
}
static int[] rotLeftRec(int[] a, int d, int numRot) {
    if (numRot >= d) {
        return a;
    } else {
        int first = a[0];
        int temp1 = NULL;
        int temp2 = NULL;
        for (int i = a.length - 1; i >= 0; i--) {
            if (i == a.length - 1) {
                temp1 = a[i];
            } else {
                if (temp1 == NULL) {
                    temp1 = a[i];
                    a[i] = temp2;
                    temp2 = NULL;
                } else {
                    temp2 = a[i];
                    a[i] = temp1;
                    temp1 = NULL;
                }
            }
        }
        a[a.length - 1] = first;
    }
    return rotLeftRec(a, d, numRot + 1);
}

Answer 1

我很好奇 arraycopy 方法，看起来像这样。每次将数组移动 n 次时，无需调用此处提出的方法 m 次。你可以用乘积 m*n 来调用它，你也在那里(我想)。如果那个通过，我会很好奇。

顺便说一句。 ArrayList 使用 arrayCopy，我从那里得到它。

static int[] rotLeft(int[] a, int d) {
    if (d < 0 || a == null || a.length == 0) {
        throw new IllegalArgumentException();
    }

    int shift = d % a.length;
    if (shift == 0) {
        return a;
    }
    int[] result = new int[a.length];
    System.arraycopy(a, shift, result, 0, a.length - shift);
    System.arraycopy(a, 0, result, a.length - shift, shift);
    return result;
}