Problem: 189. 轮转数组
题目：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(N)
整体思路
这段代码旨在解决一个经典的数组问题：旋转数组 (Rotate Array)。问题要求将一个数组中的元素向右循环移动 k 个位置。例如，将 [1, 2, 3, 4, 5] 向右移动 2 位，结果应为 [4, 5, 1, 2, 3]。
该实现采用了一种非常直观的方法：使用一个额外的数组来辅助完成旋转。其逻辑步骤清晰明了：
-
处理
k值：- 首先，代码对
k进行了取模运算k = k % n。这是非常重要的一步，因为如果k大于数组长度n，旋转k位和旋转k % n位的效果是完全相同的。例如，旋转n位等于没有旋转。这可以处理k为任意非负整数的情况。
- 首先，代码对
-
创建辅助数组：
- 创建一个与原数组
nums等长的新数组ans。这个数组将用来临时存放旋转后的结果。
- 创建一个与原数组
-
构建旋转后的数组：
- 算法将原数组
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数组中下一个要填充的位置。
- 算法将原数组
-
将结果复制回原数组：
- 当
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-1for (int i = n - k; i < n; i++) {ans[cur++] = nums[i];}// 步骤 3: 将原数组的前 n-k 个元素复制到新数组的剩余位置// 这部分元素是从索引 0 到 n-k-1for (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)
- 取模运算：
k = k % n是 O(1) 操作。 - 第一个复制循环：
for (int i = n - k; i < n; i++)执行k次。 - 第二个复制循环：
for (int i = 0; i < n - k; i++)执行n-k次。- 这两个循环合起来，总共对
nums数组进行了一次完整的遍历，将元素复制到ans。总操作次数是k + (n-k) = n。
- 这两个循环合起来，总共对
- 第三个复制循环：
for (int i = 0; i < n; i++)执行n次，将ans的内容复制回nums。 - 综合分析：
- 算法总共执行了大约
n + n = 2n次的元素复制操作。 - 因此，总的时间复杂度是线性的，即 O(N)。
- 算法总共执行了大约
空间复杂度：O(N)
- 主要存储开销：算法创建了一个名为
ans的整型数组来作为辅助存储空间。 - 空间大小：该数组的长度与输入数组
nums的长度N相同。 - 其他变量：
n,cur,k,i等变量都只占用常数级别的空间，即 O(1)。
综合分析：
算法所需的额外空间主要由辅助数组 ans 决定。因此，其空间复杂度为 O(N)。这是一个非原地（not-in-place）的算法。
【LeetCode 热题 100】189. 轮转数组——（解法二）反转数组
