题解 | #旋转数组#

##遍历赋值算法##

对于数组中每个元素我直接将它们定位到该去的位置，尽最大可能去减少了移动次数，而且只用了一个int tmp保存临时数据，但是时间复杂度上为什么还是超过不了大多数的C++提交，啊，很困惑。代码在下面，感兴趣的自己看吧。

class Solution { public: /** * 旋转数组 * @param n int整型 数组长度 * @param m int整型 右移距离 * @param a int整型vector 给定数组 * @return int整型vector */ vector solve(int n, int m, vector& a) { // write code here // 依次改变每一个值即可,但会遇到不能遍历完全的问题（当两个数不是互质时） // 先去除冗余的n m = m % n; if(m==0) return a; if(n==1) return a; int maxGroup = gcd(n,m); int start = 0; while(start<maxGroup){ int i = start; int tmpValue = a[i]; while(1){ int nextIndex = (i-m+n)%n; // 遇到第一个数时，跳出 if(nextIndex == start) break; // 否则，进行遍历赋值 a[i] = a[nextIndex]; i=nextIndex; } a[i]=tmpValue; start++; } return a; } int gcd(int m,int n){ if(m%n==0) return n; return gcd(n,m%n); } };