算法设计2——数组元素循环右移

问题描述：

有一个数组 a 包含 n (n>1) 个整数元素，设计一个尽可能高效的算法将数组 a 中的后面k个元素循环右移（k<=n），其中n是数组长度，0<=k<=n。

例如：a = （1，2，3，4，5），k=3，

结果：a = （3，4，5，1，2）

思路：

1. 理解问题：将数组 a 中的最后 k 个元素移动到数组的前面，同时保持剩余元素的顺序不变。
2. 解决问题：通过过三次反转数组的子部分解决：

• 先反转整个数组，[1，2，3，4，5] ——> [ 5，4，3，2，1 ]
• 然后反转整个数组的前 k 个元素，——>[ 3，4，5，2，1 ]
• 最后反转数组最后的 n-k 个元素。——>[ 3，4，5，1，2 ]

public static void rotateRight(int[] a, int k) {
        int n = a.length;
        k = k % n; // 处理k大于n的情况
        reverse(a, 0, n - 1); // 反转整个数组
        reverse(a, 0, n-k); // 反转数组的前k个元素
        reverse(a, k, n - 1); // 反转数组的剩余n-k个元素
}

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

时间复杂度：每次反转操作的时间复杂度是 O(n)，执行了三次反转操作，所以总的时间复杂度是 O(n)。
空间复杂度：这个算法是原地操作，不需要额外的存储空间，所以空间复杂度是 O(1)。

调用：

public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5}; // 示例数组
        int k = 3; // 需要右移的元素数量
        rotateRight(a, k); // 调用函数进行数组右移

        // 打印结果
        System.out.print("Rotated array: ");
        for (int value : a) {
            System.out.print(value + " ");
        }
    }