Leetcode 旋转数组

题目描述

一个数组A中存有N个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（M>=0）个位置。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

示例1

输入

复制

6,2,[1,2,3,4,5,6]

输出

复制

[5,6,1,2,3,4]

 

 

 

思路一：

对称思路：  将A[0,n-m]部分对换   将A[n-m,n]部分对换

最后将整个A对换

  vector<int> solve(int n, int m, vector<int>& a) {
        // write code here
          
        m=m%n;//取余数
        if(m==0)  //无需移动
            return a;
        reverse(a.begin(),a.begin()+n-m);
        reverse(a.begin()+n-m,a.begin()+n);
        reverse(a.begin(),a.end());
        return a;
}

 

 

思路二：

对于一个元素A[i]其将被移动到A[(i+k)%len]处，而该处的元素同样被往后移动k个单位

由此构成一个回环，回环最后一个位置为j  (满足 (j+k)%len==i)

最少可以一个回环完成全部移动，最多需要k个回环完成全部移动

采取的策略是每移动一次count+=1   当count==len时跳出循环

最终的时间复杂度为O(N)

  vector<int> solve(int n, int m, vector<int>& a) {
        // write code here
          
        m=m%n;//取余数
        if(m==0)  //无需移动
            return a;
        //其他情况  
        int count=0;//每移动一次count++  表示一个数被移动到正确的位置
        for(int i=0;i<m;i++)  //最多移动m轮（每一轮是一个闭环）
        {
           if(count>=n)
               break;
            //该轮 起始移动位置为 a[i]
            int k=a[i];
            int index=i;
            while(1)  //(i+m)%n为当前a[i]元素的移动目标位置
            {
                int temp=a[(index+m)%n];
                a[(index+m)%n]=k;
                count++;
                k=temp;
                 index=(index+m)%n;//index移动到下一个位置
                if(index==i)
                    break;     //若下一个考虑元素为i 即完成一个闭环

            }

            
        }
        
       return a;
        
    }