LeetCode 补拙笔记

0. 前言

• 日期：2026.06.20
• 题目：189. 轮转数组
• 难度：中等
• 标签：数组、双指针、原地反转

1. 题目理解

问题描述 给定整数数组 nums 和非负整数 k，将数组元素向右轮转 k 个位置，要求原地修改数组，不使用额外大数组。 轮转含义：末尾 k 个元素整体挪到数组最前方，剩余元素后移。

示例

输入：nums = [1,2,3,4,5,6,7], k = 3 输出：[5,6,7,1,2,3,4] 解释：末尾3个元素 5,6,7 移至数组头部。

2. 解题思路

核心观察

1. 若 k ≥ 数组长度 n，等价轮转 k % n 次，消除多余重复轮转；
2. 三次原地反转法（最优空间解法）： ① 反转整个数组； ② 反转前 k 个元素； ③ 反转后 n-k 个元素；
3. 优化方向：合并边界判断，消除反转函数内多余条件分支，简化取模边界处理。

算法步骤

1. 计算有效轮转步数 k = k % nums.length；
2. 全局反转整个数组；
3. 反转区间 [0, k-1]；
4. 反转区间 [k, n-1]；
5. 数组原地修改完成轮转。

3. 代码实现

package lc189;

import java.util.Arrays;

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        reverse(nums,0,nums.length-1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.length-1);
    }

    private void reverse(int[] arr, int left, int right) {
        while(left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}

4. 代码优化说明

class Solution {
public void rotate(int[] nums, int k) {
    int len = nums.length;
    // 取模得到有效步数，k=0时三次反转无操作，无需单独if判断
    int step = k % len;
    reverse(nums, 0, len - 1);
    reverse(nums, 0, step - 1);
    reverse(nums, step, len - 1);
}

// 双指针原地反转，仅循环判断，无多余if分支
private void reverse(int[] arr, int l, int r) {
    for (; l < r; l++, r--) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }
}
}

5. 复杂度分析

• 原始三次反转版本 时间复杂度：$O(n)$，数组每个元素仅参与两次交换；while循环实现反转，无冗余分支 空间复杂度：$O(1)$，原地修改，仅常数临时变量
• 优化后版本 时间复杂度：$O(n)$，遍历次数不变；for循环替代while，代码更紧凑，无新增条件判断 空间复杂度：$O(1)$，无额外数组，仅临时交换变量；消除k=0场景的单独if分支，逻辑自洽

6. 总结

• 核心数学技巧：三次原地反转实现数组右轮转，无需额外数组；
• 优化亮点：改用for循环简化反转逻辑，去除冗余边界if判断，变量命名可读性提升；
• 关键边界：必须对 k 取模，防止 k 大于数组长度造成无效重复反转。