Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

Follow up:

  • Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
  • Could you do it in-place with O(1) extra space?

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

进阶：

  • 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
  • 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

轮转数组，比较直接的方法就是重新开辟了一个新数组，然后复制过去，这种方法能够解决问题，但是不够巧妙。

再进一步想，可以环状替换，这种方法就比较有意思，需要一个额外的中间变量，然后实现一种环状的，前后衔接的，依次交替的更换（这种方法稍微有点复杂，动手笔画理解得可能更好）。

另外一种就比较奇特，**通过多次整体翻转的策略，**这个算法将在下文中仔细说明。

🌽上菜

方法一：使用额外数组

可以创建一个新的数组来重新排列元素。

  1. 遍历原数组，将每个元素放置到 (i + k) % n 的位置上。
  2. 将新数组复制回原数组。

这种方法的空间复杂度是 O(n)。

方法二：环状替换

这种方法可以不使用额外的空间，直接在原数组上操作：

  1. 从某个位置开始，将其元素放到正确的位置上，同时把目标位置的原元素保存下来。
  2. 继续操作新位置的元素，直到回到起始位置。
  3. 如果数组有多于一个的独立循环（例如，数组长度和 k 的最大公约数大于1），需要从数组中不同的位置开始，直到每个元素都被移动过。

这种方法的空间复杂度是 O(1)，因为它是原地操作。

用实际的例子来理解“环状替换”：

环状替换举例

1 2 3 4 需要移动 2 位，变成 3 4 1 2

从下标0开始，start = 0，prev = nums[0] = 1；（起点）

需要替换的在0 + 2的位置，next = 2，temp = nums[2] = 3；

发生替换（使用prev）：1 2 1 4；更新：prev = temp = 3；current = next = 2；

循环继续；

current = 2；需要替换的在0 + 2的位置（与nums.size()取模），current = 0；temp = nums[0] = 1；（终点，这里就又回到了起点，形成了闭环）

发生替换（使用prev）：3 2 1 4；

此时current == start，说明这一轮遍历结束，start 需要更新；

循环中止，start + 1；

从下标1开始，start = 1，prev = nums[1] = 2；（起点）

需要替换的在1 + 2的位置，next = 3，temp = nums[3] = 4；

发生替换（使用prev）：3 2 1 2；更新：prev = temp = 4；current = next = 3；

循环继续；

current = 3；需要替换的在3 + 2的位置（与nums.size()取模），current = 1；temp = nums[1] = 2；（终点，又回到了起点，形成了闭环）

发生替换（使用prev）：3 4 1 2；

此时current == start，说明这一轮遍历结束，start 需要更新；

循环中止，start + 1；

此时已经完成排序了，可以退出程序了。

具体的循环退出依据可以通过数组长度和轮转次数的最大公约数得到。

环状替换中的GCD（最大公约数）

当将数组中的每个元素向右移动 k 个位置时，可以通过 $i \rightarrow (i + k) % n$ 的映射关系来理解每个元素的新位置，其中 i 是原始索引，n 是数组的长度。

但是使用这种映射，得需要知道这种循环结构何时会回到起点，也就是形成一个闭合的循环。

  1. 循环长度和返回起点：

    • 当从某个索引 start 开始，不断应用 $i \rightarrow (i + k) % n$ 映射，我们想要知道什么时候会回到 start 索引。这就意味着寻找最小的正整数 m，使得 $(start + m \cdot k) % n = start$。简化后得到 $(m \cdot k) % n = 0$，即 $m \cdot k$ 应该是 n 的倍数。

  2. 最小的 m 值：

    • 要找到最小的 m，使得 $m \cdot k$ 是 n 的倍数，等价于找到最小的 m 使得 $\frac{m \cdot k}{n}$ 是一个整数。这意味着 m 是一个特定的值，使得 $m \cdot k$ 能够整除 n。这就需要 k 中的任何可能因子已经在 n 中有对应的因子以保证整除。
    • GCD（最大公约数）是 k 和 n 的共同最大因子。当我们通过 GCD 来除 n 和 k，实际上是在移除两者共有的所有因子，所得的比例（k/GCD 和 n/GCD）是最简形式，没有更多的公共因子。
    • 使用 GCD，我们可以重新定义 k 和 n：
      • $k’ = \frac{k}{\text{gcd}(k, n)}$
      • $n’ = \frac{n}{\text{gcd}(k, n)}$
    • 现在 $k’$ 和 $n’$ 互质（即没有共同因子），因此最小的 m 使得 $(m \cdot k’) % n’ = 0$ 就是 n'，即 $n / \text{gcd}(k, n)$。
    • 因此，$m = \frac{n}{\text{gcd}(k, n)}$ 是使得 $(i + m \cdot k) % n = i$ 成立的最小 m 值，这里的 gcd 表示 k 和 n 的最大公约数。

  3. 循环的数量：

    • 如果从数组中的每个 start 点开始都运行一个循环，通过 k 和 n 的最大公约数可以知道，从一个给定的起点开始，会在经过 $n / \text{gcd}(k, n)$ 步后回到起点。
    • 因此，要遍历所有可能的起点（确保每个元素都被移动到正确的位置），需要从 gcd(k, n) 个不同的起点开始，每个起点所经历的循环都是这个全覆盖循环的独立的一部分。

假设 n = 12 和 k = 8：

  • $\text{gcd}(12, 8) = 4$。
  • 从 0 开始的循环会经过索引 $0 \rightarrow 8 \rightarrow 4 \rightarrow 0$，形成一个长度为3的循环。
  • 因为 gcd 是 4，可以从 0, 1, 2, 3 这四个起点开始（这里也可以观察出：起点4是没必要，因为已经出现在起点为0的循环中了），每个起点都会形成一个独立的循环，这些循环共同覆盖整个数组。

计算 GCD 的方法

GCD 可以使用辗转相除法（Euclidean algorithm）来计算，这是一种高效的算法。

辗转相除法，也被称为欧几里得算法（Euclidean algorithm），是一种用于计算两个整数的最大公约数（GCD，Greatest Common Divisor）的古老算法。这个算法基于一个简单的原理：两个数的最大公约数不变，如果较大数减去较小数。更具体地说，给定两个正整数 $a$ 和 $b$，其中 $a > b$，那么 $gcd(a, b)$ 等于 $gcd(b, a - b)$。但为了效率，通常使用除法代替减法。

以下是计算 GCD 的简单函数实现：

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

基本步骤：

  1. 将较大数除以较小数。
  2. 将除法的余数替换到较小数的位置。
  3. 重复这个过程，直到其中一个数变成零。
  4. 当余数为零时，另一个数就是最大公约数。

形式上，算法可以描述为：

  • 输入：两个正整数 $a$ 和 $b$。
  • 输出：$a$ 和 $b$ 的最大公约数 $gcd(a, b)$。

比如计算 $252$ 和 $105$ 的最大公约数：

  • $gcd(252, 105)$
  • $252 \mod 105 = 42$，现在计算 $gcd(105, 42)$
  • $105 \mod 42 = 21$，现在计算 $gcd(42, 21)$
  • $42 \mod 21 = 0$，结束。所以，最大公约数是 $21$。

‼️有一点重要的点，算法本身具有自校正的特性，即使 $b$ 大于 $a$，它仍然可以正确工作。

这是因为在算法的每一步中，都是取两个数的余数来进行下一次迭代，这个过程会自动调整两个数的顺序。

如果在算法开始时 $b > a$，那么在第一次迭代中，余数将是 $a$（因为 $a \mod b = a$ 当 $a < b$），然后 $a$ 和 $b$ 的角色在下一次迭代中就会交换。这就自然地保证了接下来的迭代中较大的数总是被较小的数除，算法的逻辑不会受到初始条件的影响。

举例：

假设 $a = 18$ 和 $b = 24$，需要找到它们的最大公约数。

  1. 迭代 1:

    • $b = 24, a = 18$
    • $a \mod b = 18 \mod 24 = 18$（因为 18 小于 24）
    • 接下来，$b$ 变为 18，$a$ 变为 24。

  2. 迭代 2:

    • $b = 18, a = 24$
    • $a \mod b = 24 \mod 18 = 6$（现在按正常的逻辑进行）
    • $b$ 变为 6，$a$ 变为 18。

  3. 迭代 3:

    • $b = 6, a = 18$
    • $a \mod b = 18 \mod 6 = 0$（余数为 0，结束）
    • $gcd$ 是 6。

不论 $a$ 和 $b$ 的初始大小关系如何，欧几里得算法总能正确地调整并找到最大公约数。这也是为什么这种算法非常强大和灵活的原因之一。

欧几里得算法还可以扩展到更一般的情况，如求解线性方程、多项式的最大公约数，以及非欧几里得域（如高斯整数）的公约数计算等。还有一些变种和改进方法，包括：

  1. 扩展欧几里得算法：

    • 不仅计算最大公约数，还找到整数解 $x$ 和 $y$，使得 $ax + by = gcd(a, b)$。这在某些数论和密码学应用中非常重要。

  2. 二进制GCD算法：

    • 也称为Stein算法，这种方法不使用除法，而是基于更简单的位运算来计算最大公约数，效率在某些硬件上更优。

  3. 多项式GCD：

    • 使用类似欧几里得算法的方法来找到两个多项式的最大公共因子。

使用这个 gcd 函数，我们可以计算出 n 和 k 的 GCD，从而确定需要进行的环状替换的起始位置数。

方法三：反转数组

使用数组反转可以巧妙地实现旋转，而不需要额外的空间：

  1. 反转整个数组：这一步把数组的头部移到尾部，尾部移到头部。
  2. 反转前 k % n 个元素：由于整个数组已经被反转，最初的最后 k % n 个元素现在位于数组的前部。再次反转这部分可以恢复它们的原始顺序。
  3. 反转剩余的 n - k % n 个元素：这样可以恢复这部分元素的原始顺序。

这同样是一个空间复杂度为 O(1) 的原地算法。

举例说明

假设数组为 [1,2,3,4,5,6,7]，需要向右移动 k = 3 步。

  1. 初始数组：[1,2,3,4,5,6,7]
  2. 反转整个数组：[7,6,5,4,3,2,1]
  3. 反转前 k % n = 3 个元素：[5,6,7,4,3,2,1]
  4. 反转剩余 n - k = 4 个元素：[5,6,7,1,2,3,4]

不够轮转的k 是多少，整个操作只涉及三次数组遍历，因此时间复杂度为 $O(n)$，而且不需要额外的存储空间，空间复杂度为 $O(1)$。

核心思想

这里需要细品的是：

  1. 同样反转两次，可以复原操作
  2. 所以先整体反转，再局部反转

代码实现

// 189. Rotate Array
#include <iostream>
#include <vector>

using namespace std;

// 方法一 使用额外的数组
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        // 错误写法，自己反思一下吧
        // k = n % k;
        // 处理给的k大于n的情况
        k =  k % n; 

        vector<int> nums_new(n);
        for (int i = 0; i < n; i++) {
            // 注意这种错误写法
            // nums_new[i] = nums[i + k];
            // 肯定要从nums[0]开始，不然会越界的
            nums_new[(i + k) % n] = nums[i];
        }

        nums = nums_new;
        
    }
};

// 方法二 环状替换（循环替换）
class Solution {
public:
    // 需要计算最大公约数
    int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        int end = gcd(n, k);
        for (int start = 0; start < end; start++) {
            int current = start;
            int prev = nums[start];
            do {
                // 注意这里写错了
                // int next = (start + k) % n;
                // 因为已经知道current，start标记的是大循环
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                // 还需要更新current
                current = next;
            } while (current != start);
        }
        
    }
};

// 方法三 反转数组
// 直接使用vector的reverse方法
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;

        reverse(nums.begin(), nums.end());
        // 反转两次，顺序就会复原
        // 左闭右开区间
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};