189. 轮转数组

Bin大约 3 分钟

189. 轮转数组

题目：轮转数组

描述：

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例：

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: nums = [-1,-100,3,99], k = 2
输出: [3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

示例 3:

输入: nums = [1], k = 0
输出: [1]

解题思路

方法 1：使用额外数组

创建一个新数组 rotated，存储轮转后的结果。
将 nums 中的每个元素放入 rotated 中的正确位置：
```
rotated[(i + k) % n] = nums[i];
```
其中 n 是数组长度。
将 rotated 中的元素复制回 nums。

方法 2：原地旋转（反转法，推荐）

核心思想：
- 整体反转：将整个数组反转。
- 反转前部分：将前 k 个元素反转。
- 反转后部分：将剩下的 n-k 个元素反转。
步骤：
- 反转整个数组。
- 反转前 k 个元素。
- 反转后 n-k 个元素。

为什么这样做？

轮转数组的最终结果实际上是将后 k 个元素移到前面，前面的元素移到后面。
通过上述三次反转，可以将元素调整到正确的位置。

代码实现

方法 1：额外数组

public class RotateArray {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] rotated = new int[n];

        // 将每个元素放到新位置
        for (int i = 0; i < n; i++) {
            rotated[(i + k) % n] = nums[i];
        }

        // 将新数组复制回原数组
        for (int i = 0; i < n; i++) {
            nums[i] = rotated[i];
        }
    }

    public static void main(String[] args) {
        RotateArray solution = new RotateArray();

        int[] nums1 = {1, 2, 3, 4, 5, 6, 7};
        solution.rotate(nums1, 3);
        System.out.println(java.util.Arrays.toString(nums1)); // 输出: [5,6,7,1,2,3,4]
    }
}

方法 2：原地旋转（推荐）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        // 读取轮转步数
        int k = scanner.nextInt();

        Solution solution = new Solution();
        solution.rotate(nums, k);

        // 输出轮转后的数组
        for (int i = 0; i < n; i++) {
            System.out.print(nums[i]);
            if (i < n - 1) System.out.print(" ");
        }
        System.out.println();

        scanner.close();
    }
}

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n; // 如果 k 大于数组长度，取模处理

        // 1. 反转整个数组
        reverse(nums, 0, n - 1);

        // 2. 反转前 k 个元素
        reverse(nums, 0, k - 1);

        // 3. 反转后 n-k 个元素
        reverse(nums, k, n - 1);
    }

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

时间复杂度

方法 1：额外数组
- 创建新数组需要 O(n)，复制数组也需要 O(n)。
- 总时间复杂度：O(n)。
方法 2：原地旋转
- 反转整个数组和子数组的操作总共需要 O(n)。
- 总时间复杂度：O(n)。

空间复杂度

方法 1：额外数组
- 需要额外的数组 rotated，空间复杂度为 O(n)。
方法 2：原地旋转
- 不需要额外空间，只交换元素，空间复杂度为 O(1)。

总结

推荐方法：原地旋转（反转法），时间复杂度和空间复杂度都更优。
关键点：通过三次反转实现元素的轮转，可以高效地调整数组。