题目主要信息:

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

具体思路:

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

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

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

代码实现:

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),没有使用额外的辅助空间