跳到主要内容

LeetCode 189. 轮转数组

本节目标

用三次翻转在原数组中完成向右轮转。

这道题承接数组与区间：要把末尾的连续段移到前面，同时保持两段内部的相对顺序。

查看原题

题意与约束​

将数组向右轮转 k 步；要求直接修改输入数组。

朴素思路及瓶颈​

可以重复 k 次“保存末尾元素，再把其余元素整体右移一位”，每次轮转都要移动 n 个元素；即使先令 k %= n，最坏时间复杂度仍为 O(n²)。瓶颈是同一元素被逐步搬动多次，而目标实际上只是交换前后两个连续段，因此可以用整段翻转一次完成位置调整。

三次翻转​

先令 k %= n。翻转整个数组后，原本末尾的 k 个元素来到前面，但两段内部都倒序；再分别翻转前 k 个和其余元素，就恢复两段各自的顺序。

原地修改​

算法始终修改原数组，不创建第二个同长度数组。三次翻转依次作用于整个数组、前 k 个元素和剩余元素，因此额外空间为常数。

代码实现​

两份源码都先防御空数组，再归一化 k 并执行三次翻转。C++ 使用标准库的原地翻转；Python 用双指针交换指定闭区间，避免切片产生同长度副本。

C++17
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (nums.empty()) {
            return;
        }
        k %= nums.size();
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

复杂度分析​

时间复杂度为 O(n)，额外空间复杂度为 O(1)。

易错点​

  • 空数组先做取模，导致除零。
  • 忘记对 k 取模，轮转步数大于长度时边界错误。

模式迁移​

当一个数组变换能拆成若干连续段的重排时，先检查反转是否能在原地交换段的位置；若必须保留更多历史状态，再考虑额外数组。