189. 轮转数组

题目链接：189. 轮转数组

题目描述

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

要求：尽量想出更多的解决方案，至少有三种不同的方法可以解决这个问题。最好使用空间复杂度为 $O(1)$ 的 原地（in-place） 算法。

核心思考：三次翻转法（原地算法）

将数组向右平移 k 个位置，常规思路是开辟一个与原数组等大的新数组，将每个元素直接放置到计算后的目标映射下标位置：(i + k) % n。但这需要 $O(N)$ 的额外空间。

如果要在严格的 $O(1)$ 空间复杂度下实现原地轮转，最优解法是基于数学观察的三次翻转法。

我们可以将数组看作由两段拼起来的积木：

• 后面 k 个元素：这部分元素将会在轮转后跨越边界，跑到数组的最前面。
• 前面 n-k 个元素：这部分元素将会整体向后平移。

利用数组翻转的特性，我们可以通过三次翻转极其优雅地完成这两段积木的调换：

1. 预处理步长：因为当 k 大于数组长度 $L$ 时，跨越整圈的平移是无意义的无效操作，因此直接对 k 求余获取有效偏移量：k = k % L。
2. 第一次全局翻转：将整个数组翻转 reverse(0, L-1)。这一步将位于尾部的 k 个元素粗暴地扔到了前面，同时原本在前面的元素被转移到了尾巴上。但此时，这两段各自内部的顺序是颠倒的。
3. 第二次局部翻转：对前 k 个元素再次翻转 reverse(0, k-1)。将其内部循序正位。
4. 第三次局部翻转：对剩下的后面部分节点执行翻转 reverse(k, L-1)。彻底还原其相对顺序。

这三个步骤的组合，无需任何额外的临时数组，仅依靠双指针的原地交换，就完美达成了平移的目的。

解题思路 (Python)

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 原地算法：整体反转后两次局部反转
        def reverse(n,m):
            while n < m:
                nums[n],nums[m] = nums[m],nums[n]
                n += 1
                m -= 1
        
        l = len(nums)
        # 求余之后的次数才有价值
        k = k % l
        reverse(0,l-1)
        reverse(0,k-1)
        reverse(k,l-1)
        return

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是数组的长度。第一次全局翻转耗时大约 $N/2$ 次交换，后两次局部翻转的总和耗时也约为 $N/2$ 次交换，合共执行了 $N$ 次交换操作，时间代价为线性级别。
• 空间复杂度：$O(1)$。我们仅仅抽取了一个辅助翻转函数，全程使用双指针 n 和 m 对原数组 nums 进行原地数据交换（In-place swap），彻底抛弃了多余的临时数组载体开辟，将内存使用降至了最低水平。