BM97　旋转数组¶

中等通过率 42.44%python3核心代码模式样例通过牛客 AC数组

一句话

先整体翻转，再分别翻转前 m 个与后 n-m 个，原地 O(1) 空间。

解题思路¶

这题考什么¶

「拼接两段」这个操作能用三次翻转实现，从而绕开额外数组。右移 m 位就是把数组切成 A = a[0 : n-m] 与 B = a[n-m : n]，结果要变成 B + A。题面不许用另外的数组，于是（把 reverse 记作 rev）：

原始         A B
整体翻转     rev(A B) = rev(B) rev(A)
翻前 m 个           B  rev(A)
翻后 n-m 个         B       A      <- 正是要的结果

成立的依据是 rev(X Y) = rev(Y) rev(X)：整体一翻，两段的相对次序就换了，只是各自内部也倒了过来，再把两段各翻一次即可复原。

具体到示例 [1,2,3,4,5,6]，m = 2：

整体翻转      6 5 4 3 2 1
翻前 2 个     5 6 | 4 3 2 1
翻后 4 个     5 6 | 1 2 3 4   与期望输出一致

翻转本身用左右双指针交换，a[i], a[j] = a[j], a[i] 原地完成，全程只用常数个额外变量。每个元素恰好被碰两次，时间 O(n)。

数据规模与复杂度¶

0 < n <= 100，0 <= m <= 1000，时限「其他语言 2 秒」，题面进阶要求空间 O(1)、时间 O(n)。三次翻转合计 O(n) 次交换、O(1) 额外空间。直接写 a[:] = a[-m:] + a[:-m] 也对，但那要临时构造两段切片，空间是 O(n)，拿不到进阶分。

坑在哪¶

m 必须先对 n 取模。题面里 m 最大到 1000 而 n 只有 100，右移 n 的整数倍等于没移。不取模的话，切分点 n - m 会变成负数，两段的划分整个错位，翻转范围也跟着越界或空转。
取模前要先挡住 n <= 0，否则 m %= n 是除零错误。
取模后 m == 0 时可以直接返回：不返回也无妨（三次翻转退化成「整体翻两次再翻整段」，结果仍是原数组），但那是三趟无用的搬运。
reverse 收的是闭区间端点，三次调用的范围分别是 [0, n-1]、[0, m-1]、[m, n-1]。把哪一个的右端写成开区间，都会漏翻或多翻一个元素；尤其 [0, m-1] 的 m-1 与 [m, n-1] 的 m 必须严丝合缝地首尾相接，中间既不能重叠也不能留空。
签名要求返回 integer[]，所以原地改完之后要把 a 本身返回，不能只改不返回。

参考实现¶

solutions/nowcoder/BM97/sol.py
from typing import List, Optional


class Solution:
    def solve(self, n: int, m: int, a: List[int]) -> List[int]:
        # 取模前先挡住 n <= 0，否则下一行是除零错误
        if n <= 0:
            return a
        m %= n                       # 移动 n 的整数倍等于没动；不取模会让切分点 n-m 变成负数
        if m == 0:
            return a                 # 已经是目标形态，省掉三趟无用的搬运

        def reverse(lo: int, hi: int) -> None:
            """把 a[lo..hi] 闭区间原地翻转，两端都包含在内。"""
            # 左右双指针相向交换，只用常数个额外变量
            while lo < hi:
                a[lo], a[hi] = a[hi], a[lo]
                lo += 1
                hi -= 1

        # 三次翻转把 A B 变成 B A：整体一翻换掉两段的相对次序，再各自翻回来。
        # 三个区间都是闭区间，[0, m-1] 与 [m, n-1] 首尾相接，不重叠也不留空
        reverse(0, n - 1)            # A B      -> rev(B) rev(A)
        reverse(0, m - 1)            # rev(B)   -> B
        reverse(m, n - 1)            # rev(A)   -> A
        return a                     # 签名要求返回数组，原地改完把入参本身交回去

BM97 旋转数组¶