题解 | #旋转数组#复习一下辗转相除法 讨论一下效率
旋转数组
https://www.nowcoder.com/practice/e19927a8fd5d477794dac67096862042
主要是辗转相除法求最大公约数还给小学老师了,复习一下
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 旋转数组 * @param n int整型 数组长度 * @param m int整型 右移距离 * @param a int整型vector 给定数组 * @return int整型vector */ int gcd(int a,int b){ //最大公约数,辗转相除法 int t; while(b){ t=b; b=a%b; a=t; } return a; } vector<int> solve(int n, int m, vector<int>& a) { // write code here if(!a.size()||a.size()==1)return a; //i代表每次挪动元素数量,j代表总的挪动次数 int i,j,perRollSwaps,rollSize,curOffset,target,temp; rollSize=gcd(m,a.size()); perRollSwaps=a.size()/rollSize; for(i=0;i<rollSize;++i){ curOffset=i, temp=a[i]; for(j=0;j<perRollSwaps;++j){ target=(curOffset+m)%n; swap(temp,a[target]); curOffset=target; } } return a; } };
看起来只执行了n次交换,但是!!但是!!
实际上这样并不比通用题解里翻转三次的做法快,尽管它看起来进行了2n次交换
因为mod运算(%)实际上是非常耗费性能的,甚至需要几十个机器周期!!!所以这样看似减少了赋值操作次数,却付出了一次取模运算的代价,得不偿失
白忙活一场,但是至少复习了下小学数学qwq