題目描述

給定一個整數數組 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) 的 原地 算法解決這個問題嗎？

思考一：使用額外數組

直接計算每個元素旋轉后的新位置，借助額外數組存儲結果后再復制回原數組。

算法過程

1. 計算有效旋轉步數 k = k % n（n為數組長度）
2. 創建與原數組等長的新數組
3. 遍歷原數組，將每個元素 nums[i] 放入新數組的 (i + k) % n 位置
4. 將新數組元素復制回原數組

復雜度：時間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];}
};

思考二：環形替換

核心思路：從起始位置開始，將元素依次移動到旋轉后的目標位置，形成閉環后切換到下一個未處理的位置，直到所有元素都被移動。

算法過程

1. 計算有效旋轉步數 k = k % n，若k為0則返回
2. 初始化計數器 count = 0（記錄已處理元素數量）
3. 從索引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個元素和剩余元素，以此等價于直接旋轉的效果，避免使用額外空間。

算法過程

1. 計算有效旋轉步數：k = k % 數組長度（處理k大于數組長度的情況），若k為0則無需旋轉
2. 第一次反轉：將整個數組從索引0到末尾反轉
3. 第二次反轉：將數組前k個元素（索引0到k-1）反轉
4. 第三次反轉：將數組剩余元素（索引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--;}
}