轮转数组

LeetCode 官方题目链接

1. 题目呈现

难度等级：🟡 中等
核心考察点：数组、数学、双指针

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

---

2. 解题思路拆解

方法：数组翻转（三次翻转法）

这道题有一个非常巧妙的解法，只需要进行三次翻转操作即可完成轮转，且空间复杂度为 $O(1)$。

1. 取模：首先，如果 k 大于数组长度 n，轮转 k 次和轮转 k % n 次效果是一样的。所以先做 k = k % n。
2. 核心思想：

   • 轮转 k 次，相当于把数组的后 k 个元素移动到数组的最前面。

   • 我们可以通过三次翻转来实现：

     1. 翻转整个数组：这样后 k 个元素就到了最前面，但是顺序是反的；前 n-k 个元素到了最后面，顺序也是反的。
     2. 翻转前 k 个元素：把前面那部分反序的纠正过来。
     3. 翻转后 n-k 个元素：把后面那部分反序的纠正过来。

   • 举例：[1,2,3,4,5,6,7], k=3

     1. 整体翻转：[7,6,5,4,3,2,1]
     2. 翻转前3个：[5,6,7, 4,3,2,1]
     3. 翻转后4个：[5,6,7, 1,2,3,4] -> 结果正确！

---

3. 代码实现

/**
 * @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; // 处理 k > n 的情况
    
    // 定义翻转函数
    const reverse = (arr, start, end) => {
        while (start < end) {
            // 交换
            [arr[start], arr[end]] = [arr[end], arr[start]];
            start++;
            end--;
        }
    };
    
    // 1. 翻转整个数组
    reverse(nums, 0, n - 1);
    
    // 2. 翻转前 k 个元素
    reverse(nums, 0, k - 1);
    
    // 3. 翻转后 n-k 个元素
    reverse(nums, k, n - 1);
};

代码执行演示

输入 nums = [1, 2, 3, 4, 5, 6, 7], k = 3n = 7, k = 3

1. reverse(0, 6):
   • [1,2,3,4,5,6,7] -> [7,6,5,4,3,2,1]
2. reverse(0, 2):
   • 对 [7,6,5] 翻转 -> [5,6,7]
   • 当前数组：[5,6,7, 4,3,2,1]
3. reverse(3, 6):
   • 对 [4,3,2,1] 翻转 -> [1,2,3,4]
   • 当前数组：[5,6,7, 1,2,3,4]

---

4. 复杂度分析

维度	描述
时间复杂度	$O(n)$。每个元素最多被翻转两次，总体是线性的。
空间复杂度	$O(1)$。我们是原地修改数组，只使用了常数个额外变量。