JAVA数据结构 设计一个算法，将含有n个整数元素的数组a[0..n-1]循环右移m位，要求算法的空间复杂度为O(1)

Question

JAVA设计一个算法，将含有n个整数元素的数组a[0..n-1]循环右移m位，要求算法的空间复杂度为O(1)

Answer 1

public static void rotateArray(int[] a, int m) {
    int n = a.length;
    m %= n;

    reverse(a, 0, n - m - 1);
    reverse(a, n - m, n - 1);
    reverse(a, 0, n - 1);
}

private static void reverse(int[] a, int start, int end) {
    while (start < end) {
        int temp = a[start];
        a[start++] = a[end];
        a[end--] = temp;
    }
}

可以采用三次翻转的方式来实现将数组a循环右移m位。

具体的步骤如下：

1、将a[0..n-m-1]和a[n-m..n-1]分别进行翻转；
2、将整个数组a[0..n-1]进行翻转；
3、将a[0..m-1]和a[m..n-1]分别进行翻转。
这样就能实现将数组a循环右移m位，而且空间复杂度为O(1)。