算法进阶——旋转数组

题目

---

一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M >=0）个位置，即将A中的数据由（A0 A1 ……AN-1 ）变换为（AN-M …… AN-1 A0 A1 ……AN-M-1 ）（最后 M 个数循环移至最前面的 M 个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

数据范围0<n≤100，0≤m≤1000
进阶：空间复杂度O(1)，时间复杂度O(n)

示例1

输入：
6,2,[1,2,3,4,5,6]
返回值：
[5,6,1,2,3,4]

示例2

输入：
4,0,[1,2,3,4]
返回值：
[1,2,3,4]

思路

---

可以通过三次翻转实现。举个例子：数组[1,2,3,4,5,6]，数组长度n=6，需要右移m=2次，得到结果[5,6,1,2,3,4]。可以把数组分为两个部分，第一部分从开始到第4（n-m）个数字，也就是[1,2,3,4]，剩下的是第二部分，也就是[5,6]。先翻转第一部分，得到[4,3,2,1,5,6]。再翻转第二部分，得到[4,3,2,1,,6,5]。最后整体翻转，得到结果[5,6,1,2,3,4]。C++中翻转可以用标准库函数std::reverse。

需要注意处理m>n时的情况。此时，每动n次后数组实际上是还原了。

解答代码

---

#include <algorithm>
class Solution {
public:
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型vector 给定数组
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& a) {
        // write code here
        int i = n - m;// 分割子数组的位数
        if (n < m) {
            i = n - m % n;
        }

        // 反转前半部分数组
        std::reverse(a.begin(), a.begin() + i);

        // 反转后半部分数组
        std::reverse(a.begin() + i, a.end());

        // 整体反转
        std::reverse(a.begin(), a.end());

        return a;
    }
};