题解 | #旋转数组#

题目主要信息:

• 一个长度为$nn$的数组，将数组整体循环右移$mm$个位置（$mm$可能大于$nn$）
• 循环右移即最后$mm$个元素放在数组最前面，前$n-mn-m$个元素依次后移
• 不能使用额外的数组空间

具体思路:

循环右移相当于从第$mm$个位置开始，左右两部分视作整体翻转。即abcdefg右移3位efgabcd可以看成AB翻转成BA（这里小写字母看成数组元素，大写字母看成整体）。既然是翻转我们就可以用到reverse函数。

• step 1：因为$mm$可能大于$nn$，因此需要对$nn$取余，因为每次长度为$nn$的旋转数组相当于没有变化。
• step 2：第一次将整个数组翻转，得到数组的逆序，它已经满足了右移的整体出现在了左边。
• step 3：第二次就将左边的$mm$个元素单独翻转，因为它虽然移到了左边，但是逆序了。
• step 4：第三次就将右边的$n-mn-m$个元素单独翻转，因此这部分也逆序了。

具体过程可以参考如下图示：

代码实现:

class Solution {
public:
    vector<int> solve(int n, int m, vector<int>& a) {
        m = m % n; //取余，因为每次长度为n的旋转数组相当于没有变化
        reverse(a.begin(), a.end()); //第一次逆转全部数组元素
        reverse(a.begin(), a.begin() + m); //第二次只逆转开头m个
        reverse(a.begin() + m, a.end()); //第三次只逆转结尾m个
        return a;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，三次reverse函数的复杂度都最坏为$O(n)O(n)$
• 空间复杂度：$O(1)O(1)$，没有使用额外的辅助空间