题解 | #旋转数组#

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
        if(m==0)						//为空直接返回
            return a;

        
        m=m%n;                          //这样处理后，问题实际上就是把最后m个元素(b_1,b_2,....b_m)交换到前面
        if(m==0)                        //需要移动过的元素是0
        {
            return a;
        }
        //按m分组交换，余下的数依次交换
        int d=(n-m)/m;                  //一共分为d组
        int q=(n-m)%m;                  //剩下q（q<m)个元素依次交换几个


        int moveIndex=n-m-1;            //第一组交换的索引，每组从右到左交换
        for(int i=0;i<d;++i)            //一共交换d组
        {
            for(int j=0;j<m;++j)        //一组交换m个元素
            {
                int destinationIndex=moveIndex+m;
                //交换
                int temp=a[destinationIndex];
                a[destinationIndex]=a[moveIndex];
                a[moveIndex]=temp;

                --moveIndex;            //向左移动
            }
        }

        //余下q个元素(a_1,a_2,...a_q)与交换过来的(b_1,b_2,....b_m)依次交换
        for(moveIndex=q;moveIndex<q+m;++moveIndex)  //对每个元素b_i向前交换
        {
                int tempIndex=moveIndex;
                for(int j=1;j<=q;++j)               //对每个b_i与前面交换q次
                {
                        int temp=a[tempIndex-1];
                        a[tempIndex-1]=a[tempIndex];
                        a[tempIndex]=temp;
                        --tempIndex;
                }
        }
        return a;
    }
};

由于不能申请数组，因此只能使用交换调整，分组交换保证交换后的顺序不变。余下的逐个顺序交换即可，由于余下的是逐个与前面顺序交换，实际复杂度为O(m*(n%m)+n-m) （m<=n) 这个复杂度实际上介于O(n)到O(n^2)之间，因此余下交换还可以改良