LC189　轮转数组¶

中等通过率 48.4%python3核心代码模式普通数组样例通过牛客 AC数组数学双指针

一句话

整体翻转一次、再分别翻转前 k 个与后 n-k 个，原地完成右移 k 位。

解题思路¶

这题考什么¶

右移 k 位的效果说白了就是把数组从倒数第 k 个位置切成两段再交换顺序：

原数组   A B          A = nums[0 .. n-k-1]，B = nums[n-k .. n-1]
结果     B A

把它写成拼接就是 nums[n-k:] + nums[:n-k]，一行切片即可，但那要新开一个长度 n 的数组，是 O(n) 额外空间。题目进阶要求 O(1)。

三次翻转是把「交换两段」变成原地操作的经典手法。记 rev(X) 为把序列 X 首尾颠倒，有一条恒等式：

rev(rev(B) rev(A)) = B A

因为整体翻转会把两段的次序换过来、同时把每段内部也颠倒；再对翻转后的前 k 个（也就是 rev(B)）和后 n-k 个（也就是 rev(A)）各翻一次，把内部颠倒撤销掉，剩下的正是 B A。三步各扫一遍，总共 O(n) 次交换、O(1) 空间。翻转本身是一对相向而行的指针，见双指针与滑动窗口。

第三种做法是环状替换：从下标 0 出发，把每个元素直接送到 (i + k) % n，一路接力回到起点算一圈，起点换成 1、2、… 继续，总共走 gcd(n, k) 圈。它只写 n 次、常数最小，但圈数要靠最大公约数算，边界比三次翻转难写对。序列的原地重排手法见序列与数组。

数据规模与复杂度¶

1 <= n <= 1e5，-2^31 <= nums[i] <= 2^31 - 1，0 <= k <= 1e5。时间 O(n)：三次翻转合计交换 (n + k + n - k) / 2 = n 次。空间 O(1)。「右移一位重复 k 次」是 O(n k)，n = k = 1e5 时 1e10 次移动，不可行。

坑在哪¶

k 必须先对 n 取模。题面允许 k 到 1e5 而 n 可以只有 1，k 大于等于 n 时不取模会让翻转的切点越过数组末尾：k = 7、n = 3 时 rev(0, 6) 的下标直接出界，而正确答案与 k = 1 完全相同（转满 n 位等于没转）。
取模之后 k 可能为 0，但不需要特判。此时第二次翻转的区间是 [0, -1]（空），第三次翻转的区间是 [0, n-1]，恰好把第一次的整体翻转原样撤销回去，结果正确。多写一个 if k == 0: return 只是省几微秒，不写不会错。
返回值是 None，答案留在入参 nums 里。签名的返回类型是 void，判题机调用完之后回头读第 0 个参数（力扣元数据里的 output.paramindex 为 0）。写成 return nums 不会让判题失败，但如果误以为「返回新数组就行」而用 nums = nums[-k:] + nums[:-k] 之类的重新绑定，入参根本没被改动，判题读到的还是原数组，必错。所有写入都要落在同一个 list 对象上。
三次翻转的边界要分清：第二次翻的是 [0, k-1]（共 k 个），第三次翻的是 [k, n-1]（共 n-k 个）。把切点写成 n-k 是把「右移」做成了「左移」。
交换写成 nums[lo], nums[hi] = nums[hi], nums[lo] 在这里是安全的—— 两侧下标都是普通变量，不像 LC41 那样下标本身依赖被改的元素。
严格比对：轮转结果唯一，没有多解。

样例复核¶

nums = [1,2,3,4,5,6,7]，k = 3，n = 7，期望 [5,6,7,1,2,3,4]。切点在 n - k = 4：A = [1,2,3,4]，B = [5,6,7]。

整体翻转          [7,6,5,4,3,2,1]   这是 rev(B) 接 rev(A)
翻前 k=3 个       [5,6,7,4,3,2,1]   rev(B) 复原成 B
翻后 n-k=4 个     [5,6,7,1,2,3,4]   rev(A) 复原成 A

与样例一致。样例 2 的 nums = [-1,-100,3,99]、k = 2 同理：整体翻转得 [99,3,-100,-1]，翻前 2 个得 [3,99,-100,-1]，翻后 2 个得 [3,99,-1,-100]，与期望一致。

参考实现¶

solutions/leetcode/LC189/sol.py
from typing import List, Optional


class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        # k 可能远大于 n（题面允许 k 到 1e5 而 n 可以只有 1），
        # 不取模会让下面的切点越过数组末尾。转满 n 位等于没转，取模后语义不变
        k %= n

        def rev(lo, hi):
            # 相向双指针原地翻转闭区间 [lo, hi]；hi < lo 时是空区间，一次也不进循环
            while lo < hi:
                # 两侧下标都是普通变量，不依赖被改写的元素，可以直接用元组交换
                nums[lo], nums[hi] = nums[hi], nums[lo]
                lo += 1
                hi -= 1

        # 记 A = nums[0 .. n-k-1]、B = nums[n-k .. n-1]，目标是把 A B 变成 B A。
        # 第一步整体翻转，得到 rev(B) 接 rev(A)：段的次序已经对了，只是各自内部颠倒着
        rev(0, n - 1)
        # 第二步翻回前 k 个（就是 rev(B)），还原成 B。
        # k 为 0 时区间是 [0, -1]，空转一次，不需要特判
        rev(0, k - 1)
        # 第三步翻回后 n-k 个（就是 rev(A)），还原成 A。
        # 切点是 k 而不是 n-k：写成 n-k 就把右移做成左移了
        rev(k, n - 1)
        # 不返回任何东西：答案就留在入参 nums 这个 list 对象里，
        # 判题机调用完之后回头读它。任何形如 nums = ... 的重新绑定都不会被看见

LC189 轮转数组¶