轮转数组（中等）

方法一：简单

新建一个和原数组大小一样的新数组，用来存储移动后的数据。

就是对原数组进行for循环，把原数组i位置上面的数字移动到新数组(i+k)%nums.length位置上。

然后再把新数组上面的数赋值到原数组。

代码：

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;int[] newarr=new int[nums.length];for(int i=0;i<nums.length;i++){newarr[(i+k)%nums.length]=nums[i];}System.arraycopy(newarr, 0, nums, 0, n);}
}

方法二：

环状替换：

1. 计算有效旋转次数：k = k % nums.length（因为旋转 nums.length 次等于不旋转）。

2. 逐个替换元素：

   • 从起始位置 i = 0 开始，将 nums[i] 移动到 nums[(i + k) % n]。

   • 记录被替换的元素 prev = nums[i]，并继续替换下一个位置，直到回到起始位置。

3. 处理多个环：

   • 如果 nums.length 和 k 有公约数（即 gcd(nums.length, k) != 1），则需要处理多个环。

   • 例如，nums = [1,2,3,4,5,6], k = 2 需要 2 个环：

     • 环 1：1 → 3 → 5 → 1

     • 环 2：2 → 4 → 6 → 2

   • 因此，外层循环的次数应为 gcd(nums.length, k)

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;k = k % n; // 处理 k > n 的情况if (k == 0) return; // 无需旋转int count = 0; // 记录已替换的元素个数for (int start = 0; count < n; start++) {int current = start;int prev = nums[start];do {int next = (current + k) % n;int temp = nums[next];nums[next] = prev;prev = temp;current = next;count++;} while (current != start); // 回到起点时结束当前环}}
}