LeetCode 189. 轮转数组

对于这题，一个最直观、最简单的方法是：开一个新数组，将原数组的元素按新顺序填入新数组。

这样会有$O(n)$的空间复杂度。

还有什么办法，能够使空间复杂度降至$O(1)$？

考察一下整个交换过程，可以发现，其可以被拆解为许多"环"交叠在一起。
对任意起点 $i$，按 $i\to i+k\to i+2k\to ...(modn)$ 走，迟早回到 $i$，形成一个环。如下：

对于 nums = [1, 2, 3, 4, 5, 6, 7, 8, 9], k = 3
令start = 0
首先是 $1\to 4\to 7\to 1$，发现回到起点，结束这次操作
此时 nums = [7, 2, 3, 1, 5, 6, 4, 8, 9]
随后start++
继续操作：$2\to 5\to 8\to 2$
此时 nums = [7, 8, 3, 1, 2, 6, 4, 5, 9]
随后start++
继续操作：$3\to 6\to 9\to 3$
此时 nums = [7, 8, 9, 1, 2, 3, 4, 5, 6]
操作完成

设 $g=gcd(n,k)$，则：
环的个数 = $g$，而每个环的长度 = $n/g$

但除此以外，还有另一种方法。

把数组看成两段拼接 $A|B$：其中 $A=nums[\mathrm{0..}n-k-1]$，$B=nums[n-k..n-1]$。
右旋 $k$ 位的目标是得到 $B|A$。

用反转的性质：
先整体反转 $AB\to (AB{)}^R=B^R{A}^R$
再反转前 $k$ 个（原来的 $B^R$）得到 $B$

再反转后 $n-k$ 个（原来的 $A^R$）得到 $A$
最终就是 $B|A$。

三种方法的代码如下：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        // method 1:
        // int n = nums.size();
        // vector<int> ans(n);
        // for(int i = 0;i<n;i++){
        //     ans[(i + k)%n] = nums[i];
        // }
        // ranges::swap(nums, ans);

        // method 2:
        // int n = nums.size();
        // k = k % n;
        // int g = gcd(n, k);
        // for (int i = 0; i < g; ++i) {
        //     int current = i;
        //     int prev = nums[i];
        //     while (true) {
        //         int next = (current + k) % n;
        //         swap(nums[next], prev);
        //         current = next;
        //         if(current == i) break;
        //     } 
        // }

        // method 3:
        // int n = nums.size();
        // k = k % n;
        // ranges::reverse(nums);
        // reverse(nums.begin(), nums.begin() + k);
        // reverse(nums.begin() + k, nums.end());
    }
};