【LeetCode 热题 100】189. 轮转数组——（解法一）额外数组

Problem: 189. 轮转数组
题目：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

整体思路

这段代码旨在解决一个经典的数组问题：旋转数组 (Rotate Array)。问题要求将一个数组中的元素向右循环移动 k 个位置。例如，将 [1, 2, 3, 4, 5] 向右移动 2 位，结果应为 [4, 5, 1, 2, 3]。

该实现采用了一种非常直观的方法：使用一个额外的数组来辅助完成旋转。其逻辑步骤清晰明了：

1. 处理 k 值：

   • 首先，代码对 k 进行了取模运算 k = k % n。这是非常重要的一步，因为如果 k 大于数组长度 n，旋转 k 位和旋转 k % n 位的效果是完全相同的。例如，旋转 n 位等于没有旋转。这可以处理 k 为任意非负整数的情况。

2. 创建辅助数组：

   • 创建一个与原数组 nums 等长的新数组 ans。这个数组将用来临时存放旋转后的结果。

3. 构建旋转后的数组：

   • 算法将原数组 nums 分为两部分来处理：
     a. 后 k 个元素：这部分元素在旋转后会移动到新数组的开头。代码通过 for (int i = n - k; i < n; i++) 循环，将 nums 的后 k 个元素（从索引 n-k 到 n-1）依次复制到 ans 数组的开头（从索引 0 开始）。
     b. 前 n-k 个元素：这部分元素在旋转后会紧跟在上面那部分元素的后面。代码通过 for (int i = 0; i < n - k; i++) 循环，将 nums 的前 n-k 个元素（从索引 0 到 n-k-1）依次复制到 ans 数组的剩余位置。
   • 一个 cur 指针被用来无缝地追踪 ans 数组中下一个要填充的位置。

4. 将结果复制回原数组：

   • 当 ans 数组完全构建好后，它里面就存储了正确的旋转结果。
   • 最后，通过一个循环 for (int i = 0; i < n; i++)，将 ans 数组中的所有元素逐一复制回原数组 nums 中，以满足题目通常要求的“原地修改”。

总而言之，这是一个逻辑简单、易于理解但空间效率不高的解法。

完整代码

class Solution {
    /**
     * 将数组 nums 的元素向右循环移动 k 个位置。
     * @param nums 要旋转的整数数组
     * @param k 非负整数，表示移动的位数
     */
    public void rotate(int[] nums, int k) {
        // 获取数组的长度
        int n = nums.length;
        // 创建一个等长的辅助数组 ans，用于存储旋转后的结果
        int[] ans = new int[n];
        // cur 指针，用于追踪在 ans 数组中当前要填充的索引位置
        int cur = 0;
        
        // 步骤 1: 对 k 取模，处理 k >= n 的情况。
        // 旋转 k 位和旋转 k % n 位的效果是一样的。
        k = k % n;
        
        // 步骤 2: 将原数组的后 k 个元素复制到新数组的开头
        // 这部分元素是从索引 n-k 到 n-1
        for (int i = n - k; i < n; i++) {
            ans[cur++] = nums[i];
        }
        
        // 步骤 3: 将原数组的前 n-k 个元素复制到新数组的剩余位置
        // 这部分元素是从索引 0 到 n-k-1
        for (int i = 0; i < n - k; i++) {
            ans[cur++] = nums[i];
        }
        
        // 步骤 4: 将新数组 ans 的内容复制回原数组 nums
        // 以满足原地修改的要求
        for (int i = 0; i < n; i++) {
            nums[i] = ans[i];
        }
    }
}

时空复杂度

时间复杂度：O(N)

1. 取模运算：k = k % n 是 O(1) 操作。
2. 第一个复制循环：for (int i = n - k; i < n; i++) 执行 k 次。
3. 第二个复制循环：for (int i = 0; i < n - k; i++) 执行 n-k 次。
   • 这两个循环合起来，总共对 nums 数组进行了一次完整的遍历，将元素复制到 ans。总操作次数是 k + (n-k) = n。
4. 第三个复制循环：for (int i = 0; i < n; i++) 执行 n 次，将 ans 的内容复制回 nums。
5. 综合分析：
   • 算法总共执行了大约 n + n = 2n 次的元素复制操作。
   • 因此，总的时间复杂度是线性的，即 O(N)。

空间复杂度：O(N)

1. 主要存储开销：算法创建了一个名为 ans 的整型数组来作为辅助存储空间。
2. 空间大小：该数组的长度与输入数组 nums 的长度 N 相同。
3. 其他变量：n, cur, k, i 等变量都只占用常数级别的空间，即 O(1)。

综合分析：
算法所需的额外空间主要由辅助数组 ans 决定。因此，其空间复杂度为 O(N)。这是一个非原地（not-in-place）的算法。

【LeetCode 热题 100】189. 轮转数组——（解法二）反转数组