LeetCode 189. 轮转数组

约 5 分钟
文章信息 16 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 滴滴 小米 LeetCode 热题 100 面试经典 150 题
标签
数组 数学 双指针
目录

题目描述

✅ 189. 轮转数组

image-20220920091450540

题意分析

给定长度为 n 的数组，把每个元素整体向右挪动 k 位：原来下标 i 上的值，最终要落在下标 (i + k) % n 上，末尾溢出的部分绕回开头。题目要求「原地修改」，也就是不能把答案装进另一个数组再返回。

约束里有两个信号。第一，k 只保证非负，并不保证小于 n，因此 k 完全可能比数组还长，必须先把它和 n 的关系理清楚；第二，进阶明确点名了额外空间 $O(1)$ 的做法，这说明「开一个等长辅助数组抄一遍」虽然能过，却不是这道题真正想考的写法。

边界集中在三处：k 为 0 或恰好是 n 的倍数时，数组必须原封不动；n 为 1 时任何 k 都不改变结果；数组为空时不能对长度做取模，否则直接除零。

解法：三次反转

核心思路

问题关键：右移 k 位等价于把数组切成 A = nums[0..n-k-1]、B = nums[n-k..n-1]，再把 A + B 变成 B + A，同时保持两段内部顺序。

为什么选三次反转：辅助数组能在 $O(n)$ 时间完成，但需要 $O(n)$ 空间；环状替换虽是原地算法，却要处理多条置换环。三次反转只需一个交换变量，白板实现最短且边界清晰：

reverse(A + B) = reverse(B) + reverse(A)，再分别反转两段，就得到 B + A。

过程不变量：整体反转后，前 k 个位置恰好是 B 的逆序，剩余位置恰好是 A 的逆序；后两次反转只恢复各段内部顺序，不再改变两段位置。

正确性：第一次反转已经交换了 A、B 的相对位置；第二、三次反转分别抵消它们各自的逆序。因此每个元素都落到右移后的唯一位置，且全程只交换元素，不会丢失或重复。

解题步骤

  1. 空数组直接返回，避免随后对 0 取模。
  2. 执行 k %= n，把任意位移归一化到 [0,n-1]。
  3. 反转整个数组，再反转 [0,k-1]，最后反转 [k,n-1]。

口述样例：[1,2,3,4,5,6,7] 右移 3 位：整体反转为 [7,6,5,4,3,2,1]，再恢复前 3 位和后 4 位，得到 [5,6,7,1,2,3,4]。

代码实现

class Solution {
    public void rotate(int[] nums, int k) {
        if (nums.length == 0) {
            return;
        }

        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

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

func rotate(nums []int, k int) {
    if len(nums) == 0 {
        return
    }

    k %= len(nums)
    reverse(nums, 0, len(nums)-1)
    reverse(nums, 0, k-1)
    reverse(nums, k, len(nums)-1)
}

func reverse(nums []int, left int, right int) {
    for left < right {
        nums[left], nums[right] = nums[right], nums[left]
        left++
        right--
    }
}

复杂度分析

  • 时间复杂度：$O(n)$。三个反转区间的总长度为 2n。
  • 空间复杂度：$O(1)$，只使用下标和交换临时变量。

关键点总结

  • 循环位移先转化为相邻块交换，再选择原地反转实现。
  • k %= n 既处理超大 k，也保证两个子区间合法。
  • reverse 使用闭区间 [left,right]，调用处必须保持同一约定。
  • 若追问另一种 $O(1)$ 空间解，可说明环状替换需要处理 gcd(n,k) 条置换环，代码更易错。

易错点总结

  • 必须先判空再做 k %= nums.length，否则空数组会触发除零。
  • 忘记取模时，nums = [1,2]、k = 3 会产生非法反转区间。
  • 三个闭区间应为 [0,n-1]、[0,k-1]、[k,n-1]；把端点写成 k 或 n 会多反转一个元素或越界。
  • 辅助数组方案若只让形参指向新数组，并没有修改调用方持有的原数组，不符合原地修改要求。

相似题目

题目 难度 考察点
61. 旋转链表 中等 同样是环绕移位，但载体是链表，靠成环再断开而非反转
151. 反转字符串中的单词 中等 整体反转加逐词反转，是三次反转思想在变长块上的推广
186. 反转字符串中的单词 II 中等 要求字符数组原地完成，反转法的空间约束比本题更硬
796. 旋转字符串 简单 只判断能否由轮转得到，用拼接后子串查找代替真正的移位
面试题 01.09. 字符串轮转 简单 与 796 同型，额外限制只能调用一次字符串包含判断
48. 旋转图像 中等 二维原地重排，用转置加行反转，是「多次反转合成目标置换」的变体
剑指 Offer 58 - II. 左旋转字符串 简单 左移方向，分界点变为 n - k，可直接验证反转法的对称性