题解 | #旋转数组#

#include <vector>
class Solution {
public:
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型vector 给定数组
     * @return int整型vector
     */
    void reverse(vector<int> &a,int start,int end)
    {
        int left = start;
        int right = end;
        while(left < right)
        {
            swap(a[left], a[right]);
            left++;
            right--;
        }
    }
    vector<int> solve(int n, int m, vector<int>& a) {
        // write code here
        reverse(a,0,n-1);
        m = m % n;
        reverse(a,0,m-1);
        reverse(a,m,n-1);
        return a;
    }
};

思路：

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

具体做法:

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