LeetCode Hot 100 | 15. 轮转数组

LeetCode 189. 轮转数组 (Rotate Array)

1. 核心数学推导：三次翻转法 (The Reversal Algorithm)

这道题最经典的 $O(1)$ 空间解法通常被称为"三次翻转"。其原理并非简单的直觉技巧，而是基于群论或矩阵代数中的逆运算性质。

数学建模

我们将数组 $S$ 视为两个子向量 $A$ and $B$ 的拼接： $S = AB$ 。

$A$ ：代表前 $n-k$ 个元素（即需要向后移动的部分）。
$B$ ：代表后 $k$ 个元素（即需要移动到最前面的部分）。
目标：我们将数组从 $AB$ 变换为 $BA$ 。

定义一个翻转操作（Reverse Operation）记为 $R(\cdot)$ 或者上标 $^T$ （类比矩阵转置）。

该操作具有类似矩阵转置的性质：整体的翻转等于各部分翻转后交换位置。

$(XY)^T = Y^T X^T$

$(X^T)^T = X$

推导过程

我们需要构造一个变换序列，使得 $AB \rightarrow BA$ 。

翻转子向量 $A$ ：

$S_1 = A^T B$
翻转子向量 $B$ ：

$S_2 = A^T B^T$
翻转整体 $S_2$ ：

利用公式 $(XY)^T = Y^T X^T$ ，我们将 $S_2$ 视为 $X=A^T$ 和 $Y=B^T$ 的组合。

$Result = (A^T B^T)^T = (B^T)^T (A^T)^T$
化简：

$Result = B A$

结论：通过三次翻转，我们严格在数学上实现了向量块的交换。

2. STL 深度解析：`std::rotate`

C++ 标准库提供了 std::rotate，但其设计逻辑是基于"左旋"视角的，这导致参数理解常常反直觉。

函数原型

void rotate(ForwardIt first, ForwardIt middle, ForwardIt last);

参数含义的几何解释

first, last：定义了操作的区间 $[first, last)$ 。
middle (关键点)：指向变换后将成为第一个元素的那个位置。

std::rotate 的本质是将 middle 指向的元素移动到 first 的位置，middle 之后的所有元素紧随其后，而 first 到 middle 之间的元素则被"挤"到了末尾。

本题应用 (右旋 vs 左旋)

题目要求右旋 $k$ 步。这意味着：

原数组的倒数第 $k$ 个元素（索引为 $n-k$ ）将变成为新数组的第一个元素。
因此，middle 指针应该指向 begin() + (n - k)。

3. 代码实现

方法一：三次翻转法 (数学推导实现)

这是面试中最通用的 $O(1)$ 空间解法，完全对应上述数学推导。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n; // 必做：防止 k > n 导致的越界
        if (k == 0) return;

        // 对应公式：(A^T B^T)^T = BA
        // 1. 翻转 A 部分 (前 n-k 个) -> A^T
        reverse(nums.begin(), nums.end() - k);
        
        // 2. 翻转 B 部分 (后 k 个) -> B^T
        reverse(nums.end() - k, nums.end());
        
        // 3. 翻转整体 -> (A^T B^T)^T
        reverse(nums.begin(), nums.end());
    }
};

方法二：STL 一行流 (std::rotate)

展示对标准库迭代器操作的熟练度。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        
        // middle 指向 n-k，即原本倒数第 k 个元素
        // 该元素将被"旋转"到 begin 的位置
        std::rotate(nums.begin(), nums.begin() + (n - k), nums.end());
    }
};

方法三：辅助数组 (直觉解法)

利用取模运算直接映射，适合快速通过，但空间复杂度为 $O(N)$ 。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        vector<int> copy = nums; // 空间 O(N)
        
        for (int i = 0; i < n; i++) {
            // 下标映射公式：(i + k) % n
            nums[(i + k) % n] = copy[i];
        }
    }
};