题目描述

给定一个整数数组 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]

提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

进阶：
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗？

思考一：使用额外数组

直接计算每个元素旋转后的新位置，借助额外数组存储结果后再复制回原数组。

算法过程

计算有效旋转步数 k = k % n（n为数组长度）
创建与原数组等长的新数组
遍历原数组，将每个元素 nums[i] 放入新数组的 (i + k) % n 位置
将新数组元素复制回原数组

复杂度：时间O(n)，空间O(n)（额外数组占用）

代码

/*** @param {number[]} nums* @param {number} k* @return {void} Do not return anything, modify nums in-place instead.*/
var rotate = function(nums, k) {const n = nums.length;k = k % n;if (k === 0) return;const temp = [...nums]; // 创建原数组副本for (let i = 0; i < n; i++) {// 计算旋转后位置：原索引i的元素移到(i + k) % nnums[(i + k) % n] = temp[i];}
};

思考二：环形替换

核心思路：从起始位置开始，将元素依次移动到旋转后的目标位置，形成闭环后切换到下一个未处理的位置，直到所有元素都被移动。

算法过程

计算有效旋转步数 k = k % n，若k为0则返回
初始化计数器 count = 0（记录已处理元素数量）
从索引0开始循环：
- 记录当前位置 current 和该位置的元素 prev
- 计算目标位置 next = (current + k) % n
- 交换 prev 与目标位置元素，更新 current 为 next
- 重复上述步骤，直到回到起始位置（形成闭环）
- 计数器加1，若未处理完所有元素则从下一个索引继续

代码

/*** @param {number[]} nums* @param {number} k* @return {void} Do not return anything, modify nums in-place instead.*/
var rotate = function(nums, k) {const n = nums.length;k = k % n;if (k === 0) return;let count = 0; // 已处理的元素数量for (let start = 0; count < n; start++) {let current = start;let prev = nums[start];do {const next = (current + k) % n;[prev, nums[next]] = [nums[next], prev]; // 交换元素current = next;count++;} while (current !== start); // 回到起点时结束当前环}
};

思考三：反转数组

将数组向右旋转k步，可通过三次反转操作实现原地修改：先反转整个数组，再分别反转前k个元素和剩余元素，以此等价于直接旋转的效果，避免使用额外空间。

算法过程

计算有效旋转步数：k = k % 数组长度（处理k大于数组长度的情况），若k为0则无需旋转
第一次反转：将整个数组从索引0到末尾反转
第二次反转：将数组前k个元素（索引0到k-1）反转
第三次反转：将数组剩余元素（索引k到末尾）反转

通过三次局部反转，最终实现数组整体向右旋转k步的效果，时间复杂度O(n)，空间复杂度O(1)。

代码

/*** @param {number[]} nums* @param {number} k* @return {void} Do not return anything, modify nums in-place instead.*/
var rotate = function(nums, k) {const len = nums.length;const count = k % len;if (count === 0) return;reverse(nums, 0, len-1);reverse(nums, 0, count-1);reverse(nums, count, len-1);
};function reverse(nums, begin, end) {while (begin < end) {[nums[begin], nums[end]] = [nums[end], nums[begin]];begin++;end--;}
}