14. 旋转数组：给定一个数组，将数组向右旋转k步

旋转数组问题是一个常见的算法问题。题目要求将给定的数组向右旋转 k 步，具体来说，数组的每个元素向右移动 k 个位置，数组的末尾元素将循环到数组的开头。

1. 解题思路

要将数组向右旋转 k 步，可以考虑以下几种方法：

方法一：使用额外的数组

1. 创建一个新的数组 newArr，用于存放旋转后的结果。
2. 遍历原数组，将每个元素放置在旋转后的位置 newArr[(i + k) % n]。
3. 将 newArr 的内容复制回原数组。

时间复杂度: O(n) 空间复杂度: O(n)

方法二：使用数组翻转

1. 翻转整个数组。
2. 翻转前 k 个元素。
3. 翻转剩下的 n - k 个元素。

这种方法可以在原地完成旋转，不需要额外的数组空间。

时间复杂度: O(n) 空间复杂度: O(1)

2. 代码实现

下面是方法二（数组翻转）的 Java 实现：

public class RotateArray {

    // 主方法：旋转数组
    public static void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n; // 如果 k 大于数组长度，取模处理
        if (k == 0) return; // 如果 k 为 0，数组不需要旋转

        // 翻转整个数组
        reverse(nums, 0, n - 1);
        // 翻转前 k 个元素
        reverse(nums, 0, k - 1);
        // 翻转剩下的 n - k 个元素
        reverse(nums, k, n - 1);
    }

    // 辅助方法：翻转数组的某一部分
    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

    // 测试方法
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        int k = 3;
        System.out.println("Original array: ");
        printArray(nums);

        rotate(nums, k);
        System.out.println("Array after rotating " + k + " steps to the right:");
        printArray(nums);
    }

    // 辅助方法：打印数组
    private static void printArray(int[] nums) {
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

3. 示例解释

假设输入数组为 {1, 2, 3, 4, 5, 6, 7}，k = 3。

按照上面的方法：

1. 翻转整个数组：{7, 6, 5, 4, 3, 2, 1}
2. 翻转前 k = 3 个元素：{5, 6, 7, 4, 3, 2, 1}
3. 翻转剩余的 n - k = 4 个元素：{5, 6, 7, 1, 2, 3, 4}

最终得到旋转后的数组：{5, 6, 7, 1, 2, 3, 4}。

4. 复杂度分析

• 时间复杂度: O(n)，因为翻转数组的每一步都只需要遍历数组一次。
• 空间复杂度: O(1)，因为所有的操作都是在原数组上进行的，不需要额外的空间。

5. 总结

使用数组翻转方法可以在 O(1) 的空间复杂度和 O(n) 的时间复杂度内实现数组的旋转。这个方法简洁高效，非常适合在内存限制较大的环境中使用。